LeetCode 0142.环形链表II

环形链表II

题目描述

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

如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

示例1：

1
2
3


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

示例2：

1
2
3


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

示例3：

1
2
3


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

思路

题目要求

给定一个单链表的头节点，判断该链表是否存在环
返回环的入口

两个操作

判断是否有环
如果有环，如何找到环的入口

双指针法判断是否有环：

每次slow走一步，fast走两步。若无环，则两指针间距每次+1，fast最终为nil；若有环，则fast最终会追上slow，两个指针最终会在环中某节点相遇。

双指针法找环的入口：

此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。

假设从头结点到环形入口节点的节点数为x。环形入口节点到fast指针与slow指针相遇节点的节点数为y。从相遇节点再到环形入口节点的节点数为 z。如图所示：

相遇时：

slow指针走过的节点数为: x + y，
fast指针走过的节点数：x + n (y + z) + y ，
n为fast指针在环内走了n圈才遇到slow指针， (y+z)为一圈内节点的个数。

因为fast指针是一步走两个节点，slow指针一步走一个节点，所以fast指针走过的节点数 = slow指针走过的节点数 * 2得(x + y) * 2 = x + y + n (y + z)，两边消掉一个(x+y)得x + y = n (y + z)。因为要找环形的入口，那么要求的是x，x = n (y + z) - y 。再从n(y+z)中提出一个(y+z)，整理公式之后得x = (n - 1) (y + z) + z 注意这里n ≥ 1的，因为fast指针至少要多走一圈才能相遇slow指针。

这个公式的意义：

当n=1时，公式为 x = z。意味着fast指针在环形里转了一圈之后，就遇到了slow指针了。

这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点!

当n＞1时，意味着fast指针在环内转n圈之后才遇到slow指针。

其实这种情况和n=1的效果是一样的，一样可以通过双指针法找到环形的入口节点，只不过index1指针在环里多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

动画如下：

解题思路来自：代码随想录

代码

Go

 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


/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    slowIndex, fastIndex := head, head
    for fastIndex != nil && fastIndex.Next != nil {
        slowIndex = slowIndex.Next
        fastIndex = fastIndex.Next.Next
        // 找到环
        if slowIndex == fastIndex {
            index1 := fastIndex
            index2 := head
            // 找环的入口
            for index1 != index2 {
                index1 = index1.Next
                index2 = index2.Next
            }
            return index1
        }
    }
    return nil
}

link

GitHub