剑指 Offer II 022. 链表中环的入口节点

给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

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

示例 1：

img

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

示例 2：

img

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

示例 3：

img

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

提示：

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

思路1：集合

从头到尾遍历链表，如果集合中没有该节点就将其存入，如果集合中有该节点，证明该节点就是环的开始节点，即环的入口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode detectCycle(ListNode head) {
    HashSet<ListNode> set = new HashSet<>();
    
    ListNode cur = head;
    
    while(cur != null){
        
        if(set.contains(cur)){
            return cur;
        }
        set.add(cur);
        cur = cur.next;
    }
    return null;
    
}

思路2：快慢指针骚操作

不会快慢指针检测链表环的可以看看这篇文章：Leecode 141 环形链表

  1. 开始节点到环入口的距离我们设为A
  2. 从环入口节点到快慢指针重合的距离我们设置为B
  3. 从重合点到环入口的距离我们设为C

假设在快慢指针相遇之前快指针已经走了m圈，慢指针走了n圈，则相遇时快指针一共走了A + m(B + C ) + B步，慢指针一共走了A + n(B + C ) + B步，快指针每次比慢指针多走一个节点，即速度是慢指针的二倍，所以路程也是慢指针的二倍，所以可以得到：A + m(B + C ) + B = 2(A + n(B + C ) + B)，经过换算，可以得到A+ B = (m-2n)(B+C)。

这就说明我们从头结点到快慢指针重合节点的距离等于整数倍的快慢指针重合节点的距离到链表环入口节点的距离。

可以试着看着图动手画画理解一下：

image-20220818195624379

那既然这样的话，如果我们找到了快慢两指针相遇的节点，我们将快指针放在头结点，慢指针仍旧在原来的位置，这样我们两指针同速移动，下一次相遇是不是就是环的入口节点了呢，即都减去了B这段距离。

代码实现如下：

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
27
28
29
30
31
32
33
34
35
36
public ListNode detectCycle(ListNode head) {

    if (head == null || head.next == null) {
        return null;
    }
    //快指针
    ListNode fast = head;
    //慢指针
    ListNode slow = head;

    while (fast != null && fast.next != null) {

        fast = fast.next.next;
        slow = slow.next;
        //找到了快慢指针重合点
        if (fast == slow) {
            break;
        }

    }

    //如果快指针指向的是null，则不存在环
    if (fast == null || fast.next == null) {
        return null;
    }


    //将快指针放置在头结点，慢指针在原位置
    //同速移动
    fast = head;
    while (fast != slow) {
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
}