链表环的入口节点

快慢指针， 快指针 走了 $a+b+c+d$, 然后慢指针 走了 $a+b$, 两个指针 在 紫色点相遇。快指针一次走2步，可以列出方程 $$ a+b+c+b = 2*(a+b)\ 得到:\ a = c $$

然后 一直指针 从 起点出发，另一个 指针从 紫色点出发，同时走 a步，就可以在起点碰到

解题代码

 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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if(head==NULL || head->next == NULL) return head;
        ListNode* p = head, *q = head;
        
        while(true) {
            if(p) p = p->next;
            if(p) p = p->next;
            if(q) q = q->next;
            if(p == NULL || p == q) break;
        }
        if(p == NULL) return NULL;
        p = head;
        while(p != q) p = p->next, q = q->next;
        return p;
        
    }
};