1. question: 环形链表II（中等）
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
示例 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
解释：链表中没有环。
|
提示：
1
2
3
| 链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
|
2. answers
这道题最直观的思路是采用哈希表，遍历链表，检查当前节点是否在哈希表中，如果有，那么该节点一定是入环节点（因为环形是依次遍历的）；如果不存在，那么就将当前节点存入哈希表中。如果能够“遍历”完链表，那么就一定不存在环。
代码如下所示：
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
41
42
43
44
45
46
47
48
49
50
| public class Solution_0039 {
public static ListNode detectCycle(ListNode head) {
int index = 0;
HashMap<ListNode, Integer> hashMap = new HashMap<>();
while(head != null) {
Integer integer = hashMap.get(head);
if(integer != null) {
return head;
} else {
hashMap.put(head, index);
index ++;
head = head.next;
}
}
return null;
}
public static void main(String[] args) {
System.out.println();
ListNode ln1 = new ListNode(1);
System.out.println(detectCycle(ln1));
}
}
|
上述的方法，只有在遍历完一遍后才会发现环，因此，存储完一遍后，才会发现环。所以时间和空间复杂度均为o(n)。
参考题解，这里改进一下。
设置快慢指针，快指针以速度为2速度进行遍历，慢指针以速度为1的速度进行遍历。如果不存在换，那么快指针肯定会存在null的情况。如果存在环，那么快指针必定在某次环内“追上”慢指针，注意，因为快慢指针速度相差为1，相当于快指针以速度为1的速度靠近慢指针。所以，可根据二者是否相等（内存地址）来判断是否存在环。
那么怎么判断环入口呢？
设环入口的前面那段节点数量为a，环内的节点数量为b（a+b其实就是总节点数）。
设相遇前，慢指针走过的节点数为s，快指针走过的节点数为f，由于速度差，可得f=2s。另外，画图可知，其实快指针比慢指针多走了n个环，即f-s=nb，综上两个公式，可得s=nb。
注意，s=nb，即当慢指针的起点为入口节点时，快慢指针相遇时，走到该入口节点处。
但是实际上，慢指针的起点比入口晚了a个节点。所以，将其中一圈向后走a个节点，那么最后一圈也就向后走a个节点，即实际上快慢指针相遇的位置距离入环口处为a个节点。
因此，在相遇时，设置另一个指针，从头结点处开始移动。此时快指针以同样的速度继续移动，当二者相遇时，就是入环处。
代码如下所示：
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| public class Solution_0039_03 {
public static ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
boolean tag;
while(fast != null) {
slow = slow.next;
fast = fast.next;
if(fast != null) {
fast = fast.next;
if(fast == slow) {
tag = true;
while(head != fast) {
head = head.next;
fast = fast.next;
}
return head;
}
}
}
return null;
}
public static void main(String[] args) {
ListNode ln1 = new ListNode(4);
ListNode ln2 = new ListNode(0, ln1);
ListNode ln3 = new ListNode(2, ln2);
ListNode ln4 = new ListNode(3, ln3);
ln1.next = ln3;
ListNode result = detectCycle(ln4);
if(result == null) {
System.out.println("无");
} else {
System.out.println(result.val);
}
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
