思路

这题要用到数学的思路,根据141.环形链表,我们能够知道快慢指针可以判断它是否是环形,并且能够得出相遇的位置,现在我们知道头结点和相遇的地点,我们画图解析一下

1
假设a为头结点,b为入口,c为相遇点
image-20241105111043233

先画一圈的展示

image-20241105111234166

路程:

  • s : ab+bc

  • f : ab+n*环+bc

  • 当s绕多于一圈时我们把s和f减掉多的圈数,这样就可以只考虑上图所示,不用考虑那么多

  • 又有: 2s=f

  • 所以: 2ab+2bc=ab+n(bc+cb)+bc

  • 转为:

    1
    2
    ---> ab+bc=n(bc+cb)
    ---> (n-1)bc+ncb=ab

  • 这样之后我们可以列举来说明

    1
    2
    3
    4
    5
    6
    7
    8
    9
    当n=1:
    	cb=ab
    	我们设两个指针指向a和c,同样一步一步走,当他们相遇时就是入口
    当n=2:
    	bc+2cb=ab
    --->1环+cb=ab
    --->我们设两个指针指向a和c,同样一步一步走,当他们相遇时依然是入口
    ......
    以此类推

  • 因此,这题就是要设指针,向前走相遇,即可得到答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct ListNode *detectCycle(struct ListNode *head) {
    if (!head) return NULL;

    struct ListNode *fast = head, *slow = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            struct ListNode *start = head;
            while (start != slow) {
                start = start->next;
                slow = slow->next;
            }
            return start;
    }
    }
    return NULL;
}