首页 > 代码库 > LeetCode: Linked List Cycle
LeetCode: Linked List Cycle
LeetCode: Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
地址：https://oj.leetcode.com/problems/linked-list-cycle/
算法：将链表的指针倒过来，如果最后循环终点是原来链表的头节点，说明链表有环，如果循环的终点不是链表的头节点，那么说明链表没有环（只有一个节点的链表要单独判断）。例如，有如下链表：1->2->3->4->5->6->4(有环的链表，从最后一个节点6又指回第4个节点)，将链表的指针倒过来后变成：1->2->3->4<-5<-6<-4(表示第4个节点指像第6个节点)，注意前面四个节点的顺序被倒置了两次，因为如果有环的话循环会回到第4个节点，然后从第4个节点又循环到头节点。这里不足的地方是改变了原来的链表，但如果你再次从头节点开始将链表指针在倒置一次则又会回到原来的链表。代码：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 bool hasCycle(ListNode *head) {12 if (!head)13 return false;14 if(!head->next)15 return false;16 if(head->next == head)17 return true;18 ListNode *p = head;19 ListNode *pre = NULL;20 ListNode *old_head = head;21 head = NULL;22 while(p){23 pre = p;24 p = p->next;25 pre->next = head;26 head = pre;27 }28 if(pre == old_head)29 return true;30 return false;31 }32 };上述的方法可以利用常数空间来判断一个链表是否存在环，但如果题目要求找到这个环的起点，那么上述方法应该无法利用常数空间来解决了。以下的方法是参考网上的答案，这种方法不仅可以判断一个链表是否存在环，而且可以找到该环的起点节点。具体的思想：初始化两个指针，一个为slow，一个为fast，二者的初始值都为表头节点，然后每次让slow往后走一个节点，fast往后走两个节点。若没有环，则二者肯定不会相遇；若存在环，则二者肯定会在环中某个节点相遇。证明如下：
假设从表头节点到环开始的节点长度为a，环的总长度为k，设slow在所在节点距离环开始处的距离为b，由于slow每次只走一步，则b的取值范围为[0,k-1]，
另外设c=k-b。举个例子，假如链表为1->2->3->4->5->6->4，则a=3，k=4，若slow位于第4个节点，则b=0，c=4；若slow位于第6个节点，则b=3，c=1。现在假设slow走的总步数为a+b+tk，其中t表示slow在环中循环了t次，那么由于fast走的步数是slow的两倍，故fast走的总步数为2(a+b+tk)，所以fast将停留的节点距离环开始的节点距离为a+2b，现在假如我们能够找到一个自然数n，使得a+b=nk，那么我们就可以保证fast停留的位置与slow的位置一样。很显然，由于b可以取0到k-1中的任意值，故无论a为何值，我们总能找到一个满足a+b=nk的b值，即slow指针和fast指针最终必定会相遇。具体代码如下：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 **/ 9 class Solution {10 public:11 bool hasCycle(ListNode *head) {12 if (!head || !head->next){13 return false;14 }15 if (head->next == head){16 return true;17 }18 ListNode *fast = head;19 ListNode *slow = head;20 while(fast && slow){21 slow = slow->next;22 fast = fast->next;23 if(fast) fast = fast->next;24 if(fast == slow){25 break;26 }27 }28 if(fast)29 return true;30 else31 return false;32 }33 };Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?
地址：https://oj.leetcode.com/problems/linked-list-cycle-ii/
算法：第二题与第一题不同的是，不仅要判断链表是否存在环，而且如果存在环的话还要找到环开始的起点。这里所用的方法也是接上面的方法，假如存在环的话，那么利用上面的方法，slow跟fast能够在环当中的某个节点相遇，并且跳出循环。此时，固定住fast不变，将slow设置为表头节点，然后让二者同步的往后走，则在经过a步后二者必定相遇，且相遇的节点必为环的开始节点。证明如下：
假设经过第一题的方法后，slow和fast在距离环开始节点为b时相遇，另在假设fast指针经过a步后绕环走了t圈，并且最终停留在距离环开始节点为d时停下来，现在我们要证明的是d=0。根据题意可知
d=a-tk-c=a-tk-(k-b)=a+b-(t+1)k，根据上面一题的证明可知a+b能够被k整除，故d一定等于零，也就是说fast在经过a步后一定停留在环开始的节点。第二题代码：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode *detectCycle(ListNode *head) {12 if (!head || !head->next){13 return NULL;14 }15 if (head->next == head){16 return head;17 }18 ListNode *fast = head;19 ListNode *slow = head;20 while(fast && slow){21 slow = slow->next;22 fast = fast->next;23 if(fast) fast = fast->next;24 if(fast == slow){25 break;26 }27 }28 if(fast != slow){29 return NULL;30 }31 slow = head;32 while(fast != slow){33 fast = fast->next;34 slow = slow->next;35 }36 return fast;37 }38 };
LeetCode: Linked List Cycle