Code & Func

第35天。

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

这道题是判断链表是否有环的升级版。

首先肯定需要fast和slow指针来先判断是否有环，如果没有，就直接返回nullptr即可。

然后就是怎么计算出环的入口了。

先来个暴力的方法:

1
ListNode *detectCycle(ListNode *head) {
2
    vector<ListNode *> lvec;
3
    ListNode *fast = head;
4
    ListNode *slow = head;
5
    while(fast && fast->next) {
6
        fast = fast->next->next;
7
        slow = slow->next;
8
        //lvec.push_back(slow);
9
        if (slow == fast) {
10
            lvec.push_back(slow);
11
            slow = slow->next;
12
            while(slow != fast) {
13
                lvec.push_back(slow);
14
                slow=slow->next;
15
            }
9 collapsed lines
16
            for(auto t:lvec) cout << t->val << endl;
17
            while(find(lvec.begin(),lvec.end(),head) == lvec.end())
18
                head = head->next;
19
            return head;
20
        }
21
    }
22

23
    return nullptr;
24
}

当然实际的方法不用那么麻烦：

1
ListNode *detectCycle(ListNode *head) {
2
    vector<ListNode *> lvec;
3
    ListNode *fast = head;
4
    ListNode *slow = head;
5
    while(fast && fast->next) {
6
        fast = fast->next->next;
7
        slow = slow->next;
8
        if (fast == slow) {
9
            slow = head;
10
            while(slow != fast) {
11
                slow = slow->next;
12
                fast = fast->next;
13
            }
14
            return fast;
15
        }
4 collapsed lines
16
    }
17

18
    return nullptr;
19
}

emmmm,一直很好奇为什么可以这样判断，就去搜了一下，发现了这个判断单向链表是否有环及求环入口的算法数学证明.