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

141. 环形链表

142. 环形链表 II

题目描述

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

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

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

输入输出

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

基本思路

  1. 设置快慢两个指针p1和p2，两者在不同位置出发，慢指针走一步，快指针走两步直到两指针相遇
  2. 记下相遇指针位置，两指针一个从这里出发，另一个从头结点出发，再次相遇时为所求结点

Attention: 代码#17此处若是p1=head p2=head.next则会超时

java实现

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null || head.next.next == null){
            return null;
        }
        ListNode p1 = head.next, p2 = head.next.next;
        while(p1 != p2){
            if(p2.next == null || p2.next.next == null){
                return null;
            }
            p1 = p1.next;
            p2 = p2.next.next;
        }
        p2 = head;
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}