leetcode_linked_list_cycle_ii

发表于

难度：Medium

解题思路：

    a    f
b            e
    c    d

假设在圆圈中，有两个点slow、fast，每次slow走一步，每次fast走两步。则在一圈的步数之内，fast一定能和slow重合，因为他们的距离小于一圈的步数，每次fast追上一步。


                    a    f

                b            e

dummy    x    y        c    d

假设slow和fast从dummy开始走，直到重合。slow走了x步，fast走了2x步。直线距离设为a，slow在圆上走了b，走一周圆的距离为c。则a+b=x, a+b+c=2x。得知走一周圆的距离为x。
此时令slow从dummy出发走x步。再令cur为dummy，slow和cur此后每走一步，重合的地方即为进入圆的起始点。

代码如下：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * 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) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *slow = dummy;
        ListNode *fast = dummy;
        int count = 0;
        bool has_cycle = false;
        while(fast->next != NULL && fast->next->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
            count++;
            if(slow == fast)
            {
                has_cycle = true;
                break;
            }
        }
        if(has_cycle)
        {
            slow = dummy;
            while(count-->0)
            {
                slow=slow->next;
            }
            ListNode* cur = dummy;
            while(true)
            {
                if(cur == slow)
                {
                    return cur;
                }
                else
                {
                    cur = cur->next;
                    slow = slow->next;
                }
            }
        }
        else
        {
            return NULL;
        }
    }
};

运行结果：9ms，超过61.2%