题目

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明： 不允许修改给定的链表。

示例 1：

输入：head = [3, 2, 0, -4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

方案一（hash表）

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }

    m := make(map[*ListNode]int)
    i := 0
    node := head
    for node.Next != nil {
        if _, ok := m[node]; ok {
            return node
        }
        m[node] = i
        i += 1
        node = node.Next
    }
    return nil
}

方案二（快慢指针、Floyd 算法）

Floyd 的算法被划分成 两个不同的阶段。在第一阶段，找出列表中是否有环，如果没有环，可以直接返回 null 并退出。否则，用 相遇节点 来找到环的入口。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }

    // 快慢指针检测环，得到相遇位置
    //     slow, fast := head, head.Next
    //     for fast != slow {
    //         if fast.Next == nil || fast.Next.Next == nil {
    //             return nil
    //         }
    //         fast = fast.Next.Next
    //         slow = slow.Next
    //     }

    // 快慢指针检测环，得到相遇位置
    slow, fast := head.Next, head.Next.Next
    for slow != fast {
        if fast == nil || fast.Next == nil {
            return nil
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    meet := fast
    // 检测环入口位置
    for head != meet {
        head = head.Next
        meet = meet.Next
    }
    return meet
}

• 注意注释的位置：如果使用注释的位置的确可以检测出来有环，但是相交的点无法检测出入口的位置。
• 算法原理参考: https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode/
  • 注意快慢指针的起点，上述代码中被注释掉的虽然可以找到环，但是无法利用相遇的位置检测出环的入口。

原文

https://leetcode-cn.com/explore/learn/card/linked-list/194/two-pointer-technique/745/