题解 | #链表中环的入口结点#

完整的数学证明

O --- 非循环链表的长度

L --- 循环链表的长度

K --- 从循环链表入口节点，到快慢节点的相遇节点的长度

依照2倍的关系得出 2(O+k) = O+nL+k --- 其中n是指快指针的循环次数

得出 2O+2k = O+nL+k

O=nL-k

O= (n-1)L + (L-k)

快指针从k出发，经过L-k后，正好到达了入口节点。

重新回头审视一下，快指针处于环中的k，慢指针从头开始。经过(n-1)L 圈后，快指针还是处于k位置。此时慢指针再走L-k，快指针再走L-k，就会合到了入口节点。

package main

func EntryNodeOfLoop(pHead *ListNode) *ListNode{
    if pHead == nil || pHead.Next == nil {
        return nil
    }
    // 快慢指针
    fast := pHead
    last := pHead
    
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        last = last.Next
        if fast == last {
            break
        }
    }
    // 第一次相遇
    if last == nil || fast == nil {
        // 无环
        return nil
    }
    last = pHead
    for last != fast {
        last = last.Next
        fast = fast.Next
    }
    return last
}