题目15：链表中倒数第K个结点

题目：输入一个链表，输出该链表中倒数第K个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第一个结点。例如一个链表有6个结点，从头结点开始他们的值依次是1,2,3,4,5,6。这个链表的倒数第3个结点是值为4的结点。

//链表结点的定义： #include<iostream> using namespace std; struct ListNode { int m_value; ListNode *m_next; }; //倒数第K个结点，1. K<0 2.K>结点长度 ListNode* FindKNode(ListNode *pListNode,unsigned int k) { int n;//链表中节点的个数 则倒数第K个结点 正着数是第n-k+1个结点。此时需要遍历2次 /*若只想遍历1次时，设定两个指针p1 p2 ,俩指针之间的差距为 k-1，则当p1指向最后一个 结点时，p2正好指向倒数第k个结点。 */ if(k<=0||pListNode==NULL) return NULL; ListNode *p1=pListNode,*p2=NULL;//指针创建时必须进行初始化. for(int i=0 ;i<k-1;i++) {//若链表的结点 <k ,在for 循环中遍历表可能会出现指向NULL的m_next。 if(p1->m_next!=NULL) p1=p1->m_next; else return NULL; } p2=pListNode; while(p1->m_next!=NULL){ p1=p1->m_next; p2=p2->m_next; } return p2; }

应用一：求链表的中间结点。 如果链表中结点的总数为奇数，返回中间结点，如果节点总数为偶数，返回中间两个结点的任意一个。 思路： 可以定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个指针一次走两步。当走的快的指针走到链表的末尾时，走的慢的正好在链表的中间。 这么理解：slow节点：走了X个节点---L/2; fast节点：走了2x个几点-----L长度。共X步 引申：如何找出链表的前第1/3个链表长度的节点。就是:slow: x步---L/3节点。fast: L节点。所以，fast每次走三步。

//求链表的中间节点 ListNode* theMiddleNode(ListNode *head) { if(head==NULL) return NULL; ListNode *slow=head,*fast=head; //如果要求在链表长度为偶数的情况下，返回中间两个节点的第一个，可以用下面的循环条件 //while(fast && fast->next != NULL && fast->next->next != NULL) while(fast!=NULL&&fast->m_next!=NULL)//奇数的情况 { slow=slow->m_next;//慢的每次走一个结点 fast=fast->m_next->m_next;//快的每次走两个结点 } return slow; //慢指针所指的为中间结点 }

应用二：判断一个单向链表是否形成了环形结构。 定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个一次走两步，如果走的快的追上走的慢的指针，那么就是环形；如果走的快的指针走到了链表的末尾（m-next）都没有追上第一个指针，那么就不是环形。 思路： 用两个指针，Slow，Fast，就是一个慢一个快

慢的一次跳一步，快的一次跳两步，什么时候快的追上慢的了就表示有环（Slow == Fast ）。

bool find_cicle(ListNode *head) { bool circle=false; if(head==NULL) return NULL; ListNode *slow=head,*fast=head; while(fast!=NULL&&fast->m_next!=NULL) { fast=fast->m_next->m_next; slow=slow->m_next; if(fast==slow) { circle=true; break; } } return circle;//true 为有环， false 为无环 ，NULL 为空。 }