leetcode-142 环形链表

题目描述:给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

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

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

代码实现

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
37
38
39
40
class Solution {
public ListNode detectCycle(ListNode head) {
//1. 判断是否有环
ListNode fastNode = head;
ListNode slowNode = head;
while (fastNode != null && fastNode.next != null) {
fastNode = fastNode.next.next;
slowNode = slowNode.next;
if (fastNode == slowNode) {
break;
}
}

//2. 说明没环,直接返回null
if (fastNode != slowNode || fastNode == null || fastNode.next == null) {
return null;
}

//3. 计算环大小
int cycleSize = 1;
fastNode = fastNode.next.next;
slowNode = slowNode.next;
while (fastNode != slowNode) {
fastNode = fastNode.next.next;
slowNode = slowNode.next;
cycleSize++;
}

//4. 快指针先走环大小步,然后和慢指针一起走,会在环开始位置相遇
fastNode = slowNode = head;
while (cycleSize-- != 0) {
fastNode = fastNode.next;
}
while (fastNode != slowNode) {
fastNode = fastNode.next;
slowNode = slowNode.next;
}
return fastNode;
}
}