Linked List Cycle

LeetCode
,

第35天。

今天的题目是Linked List Cycle II:

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

    return nullptr;
}

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

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

    return nullptr;
}

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