给定一个链表的头节点head, 返回链表开始入环的第一个节点。. 如果链表无环, 则返回 null.
如果链表中有某个节点, 可以通过连续跟踪next指针再次到达, 则链表中存在环. 为了表示给定链表中的环, 评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从 0 开始). 如果pos是-1, 则在该链表中没有环.
注意: pos不作为参数进行传递, 仅仅是为了标识链表的实际情况. 不允许修改链表。
示例 1:
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2:
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
提示:
- 链表中节点的数目范围在范围 [0, 104] 内
- -105 <= Node.val <= 105
- pos 的值为 -1 或者链表中的一个有效索引
思路
这道题首先想到的方法是使用Set去重来判断是否有环以及环的入口在哪个位置.
第二种方法是双指针法(快慢指针), 设置两个指针(slow and fast), slow指针每次前进一个节点, fast指针每次前进两个节点, 只要链表中有环, 它们就一定会相遇.
在这道题中的问题是如何确定环的入口. 可以将链表分为三个部分, 分别是从头节点到环入口的节点数x, 从环入口到fast指针和slow指针相遇的节点数为y, 从相遇节点到环入口的节点数z.
这样相遇时, slow指针走过的节点数为x + y, fast指针走过的节点数为x + y + n(y + z), 这里的n指的是fast指针走了n圈才遇到slow指针, (y + z)表示一个圈内的节点数.
由于fast一次走两个节点, slow一次走一个节点, 所以fast走过的节点数 == slow走过的节点数 * 2
也就是: (x + y) * 2 = x + y + n(y + z), 简化后为x = n(y + z) - y, 最后得到x = (n - 1) * (y + z) + z
由于fast至少走一圈才可以遇到slow指针, 所以n必定大于等于1. 当n == 1时, 公式化简为x = z
也就是从头节点出发一个指针, 从相遇节点出发一个指针, 两指针每次走一个节点, 相遇处即为环形入口节点.
代码实现
HashSet:
/**
* 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) {
return null;
}
ListNode temp = head;
Set<ListNode> set = new HashSet<ListNode>();
while(temp != null) {
if(set.contains(temp)) {
return temp;
} else {
set.add(temp);
}
temp = temp.next;
}
return null;
}
}
快慢指针:
/**
* 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) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if(slow == fast) {
ListNode tempNode1 = fast;
ListNode tempNode2 = head;
while(tempNode1 != tempNode2) {
tempNode1 = tempNode1.next;
tempNode2 = tempNode2.next;
}
return tempNode1;
}
}
return null;
}
}