目录
判断链表是否有环
验证fast和slow是否会相遇
求环的长度
返回链表开始入环的第一个节点
判断链表是否有环
这是一道OJ题：环形链表
我们需要判断一个链表是否带环，带环的链表如下图：
可以看出，我们绝不可以去遍历一天带环链表，如果遍历一个循环链表，程序就会死循环
解决思路如下：
定义slow和fast指针，从头开始走，slow指针每次走1步，fast指针每次走2步
struct ListNode *fast = head; struct ListNode *slow = head;
1
2
这时的情况如下图：
然后指针开始运动，fast入环时，slow一定还没入环
然后继续运动，slow入环时：
继续运动，fast再次入环，这时在环中，slow在前，fast在后，fast追slow
最后，fast追上slow,fast == slow
所以代码如下：
bool hasCycle(struct ListNode *head) { struct ListNode *fast = head; struct ListNode *slow = head; while(fast&&fast->next) { slow = slow->next; fast = fast->next->next; if(slow==fast) { return true; } } return false; }
那为什么slow一次走一步，fast一次走两步，就一定能相遇呢？
下面我们来验证一下
验证fast和slow是否会相遇
slow一次走一步，fast一次走两步，它们是否会相遇，是否会错过？
首先，两个指针从头开始运动，首先fast入环，后来slow也入环，此时，假设fast和slow之间的距离为N
slow进环以后，fast开始追击slow，slow一次走一步，fast一次走两步，它们之间的相对距离每次都减1
说以slow一次走一步，fast一次走两步，一定能追上
也说明只要slow和fast之间的距离每次减1，就一定能追上
那么slow一次走1步，fast一次走x(x>=3)步,fast和slow会相遇吗？
下面来验证：
我们以slow一次走1步，fast一次走3步为例
这样它们之间的距离每次减2
这样，就会有2种情况：如果N为偶数，那么就会相遇，如果N为奇数，指针还需要继续运动
那fast和slow距离为-1是怎么导致的呢？
slow走一步，fast走3步，fast从后面超过slow，但是slow == fast没有发生，所以这时的距离就为-1
这时，slow和fast的距离实际上为环的长
度-1
接下来我们看看slow一次走1步，fast一次走4步
求环的长度
在前面我们已经可以验证链表是否带环，同时也找到了slow和fast相遇的位置
所以想求环的长度，只需从相遇点开始，让slow再走一圈，设置计数器，就可以得到环的长度
int CycleSize(struct ListNode* head) { struct ListNode* fast = head; struct ListNode* slow = head; int size = 0; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { struct ListNode* meet = slow; do { slow = slow->next; size++; } while (slow != meet); } } return size; }
表开始入环的第一个节点
这也是一道OJ题，链接：环形链表 II
做这道之前我们要证明一个结论
所以就可以根据这个结论，写出代码
先找到相遇点，然后让一个指针从起始点出发，一个指针从相遇点出发，最后返回这两个指针的相遇点
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *fast,*slow; fast = slow = head; while(fast&&fast->next) { slow = slow->next; fast = fast->next->next; if(slow==fast) { struct ListNode * meet = slow; struct ListNode * start = head; while(meet!=start) { meet = meet->next; start = start->next; } return meet; } } return NULL; }
这题还有另一种解法
将相遇点断开，然后用相交链表的解法
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *cur1,*cur2; cur1 = headA; cur2 = headB; int lenA = 0,lenB = 0; while(cur1->next) { cur1 = cur1->next; lenA++; } while(cur2->next) { cur2 = cur2->next; lenB++; } if(cur1!=cur2) { return NULL; } int gap = abs(lenA-lenB); struct ListNode*longer = headA; struct ListNode*shorter = headB; if(lenA<lenB) { longer = headB; shorter = headA; } while(gap--) { longer = longer->next; } while(longer!=shorter) { longer = longer->next; shorter = shorter->next; } return longer; } struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *fast,*slow; fast = slow = head; while(fast&&fast->next) { slow = slow->next; fast = fast->next->next; if(slow==fast) { struct ListNode * meet = slow; struct ListNode * st1 = meet->next; struct ListNode * st2 = head; meet->next = NULL; return getIntersectionNode(st1,st2); } } return NULL; }
