环形链表

发表于

一个含有循环链表的链表怎么求它开始循环的入口？
给出一个循环链表的例子：
1->2->3->4->5->3 最后5又指向了3，也就是说3->4->5->3形成了一个环
假设非环形的长度是x, 环形的长度是y, 链表总长度是n = x + y
思路：
两个指针， fast一次走两步， slow一次走一步， 总有一次他们会在环的某一个位置相遇。
于是可以列出关系表达式：
fast = 2slow (一个走一步，一个走两步，走了相同的时间)
fast = slow + ny (fast比slow多走了n圈的环)
2slow = slow + ny -> slow = ny
得出了关键的表达式： slow = ny, 假设一下slow处于环形起点的时候，n*y 圈之后还会回到起点。但是，slow是从链表的起点开始的，所以从入口要回退x步， 就是fast和slow相遇的点， 也就是说 非环形的链表长度x 等于 fast和slow最后相遇的节点到环形入口的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == NULL || fast->next == NULL) 
            return NULL; 
        fast = head;
   
        while(fast != slow) {
            fast = fast->next;
            slow = slow->next;
        } 
        return fast;
    }
};