Leetcode专题[链表]-142-环形链表 II

力扣链接：
https://leetcode-cn.com/probl...
解题思路：

1. 题干：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
2. 这道题其实是个数学证明题，当时记得18年找工作面试百度的时候遇到过，这里做一个思路的记录
3. 要找到环形列表的入口首先通过寻找链表的环，找到快慢指针的相遇点
4. 然后从相遇点作为一个指针，链表开头做一个指针，同时开始遍历，当他们两个相遇时，就是环的入口

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 首先判断链表是否有环
// 定义两个指针，快指针每次走两步，慢指针每次走一步，相遇就说明链表有环
// 记录相遇的位置，重新定义两个指针，一个指向头指针，一个指向之前相遇的位置
// 同时遍历，相遇的位置就是环的入口
func detectCycle(head *ListNode) *ListNode {
    fast, slow := head, head
    for fast != nil && fast.Next != nil { // 当前节点不为空，当前节点的下一节点不为空
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow { // 找到相遇的节点,说明有环
            circleStart := fast
            listStart := head
            for (circleStart != listStart) {
                circleStart = circleStart.Next
                listStart = listStart.Next
            }
            return circleStart  // 相遇时就是入口
        }
    }
    return nil
}