142.求环形链表的环节点（环形链表 II）

Title: Linked List Cycle II

Description:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example:

nput: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Difficulty:

Medium

Implement Programming Language:

Go

Follow up:

Can you solve it without using extra space?

Answer:

题目最后标注了，可否考虑不适用额外的内存空间，所以我理解的实现就是希望用快慢指针了，虽然耗子叔说不喜欢这个解法，但是我还是写一下吧，哈哈。

首先快慢指针确定是否有环，这个没太多问题。最主要的是确定有环之后，如何找到对应的环开始点，这里有一个小的数学推导，share一下。

image.png

如图所示，相遇节点上面，慢指针走了a+b，快指针走了2(a+b), 所以如果按照1步的速度，再走a+b步一定可以到碰撞节点，有一半的地方是b，所以未画出来的部分就是a了，所以再拿一个指针，走a步，正好能跟另一个指针碰在一起，在交环的地方。

代码：

func detectCycle(head *ListNode) *ListNode {
    slow,fast := head,head
    hasCycle := false
    for slow != nil && fast != nil && fast.Next != nil{
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow{
            hasCycle = true
            break
        }
    }
    if !hasCycle{
        return nil
    }

    slow = head

    for fast != slow{
        fast,slow = fast.Next,slow.Next
    }
    return slow
}