Cinte's Leetcode Record
0%

142. Linked List Cycle II

Posted on Edited on In Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

142. Linked List Cycle II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> set;
        int i = 0;
        while(head)
        {
            if(!(set.emplace(head).second))
            {
                return head;
            }
            head = head->next;
        }
        return nullptr;
    }
};

T(n) : O(n)
S(n) : O(n)

使用linked cycle中的two point 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head) return nullptr;
        ListNode* walker = head;
        ListNode* runner = head;
        
        bool isMeet = false;
        while(runner->next && runner->next->next)
        {
            walker = walker->next;
            runner = runner->next->next;
            if(walker == runner)
            {
                isMeet = true;
                break;
            }
        }
        
        if(isMeet)
        {
            walker = head;
            while(walker != runner)
            {
                walker = walker->next;
                runner = runner->next;
            }
            return runner;
        }
        return nullptr;
    }
};

image.png 即当一个点从第一次遇见的点开始，走r-m步，走到环的起始点时，另一个点刚好从起点走到环的起始点

针对最后取为1的修订 

1
Smart solution. But replacing all "wake" to "walk" in your words makes me feel better :) Another minor point is you can't just "here we takes n = 1" even it doesn't affect the last result. It still should read as s=nr-m. That means the 1st pointer starts from beginning of the list while the 2nd pointer starts from meet point, they will meet in the cycle point but the 2nd pointer walked n times of the cycle.
第二次循环时候，runner是走了r2-2r1(设为n)圈，这个数字为正即可，因为不管他多走几圈都影响不了结果。而r2是runner走的圈数，r1是walker走的圈数。

k为步数，s为起点到环起点的距离，m为圈长 r2 = (2k - s) / m，而r1 = (k - s) / m，则r2 / r1 = 2 + s/k+s，所以r2 - 2r1 = s / k + s必定为正数