文章收录于LeetCode专栏
LeetCode地址
环形链表II
题目
给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null。
为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从0开始）。如果pos是-1，则在该链表中没有环。
注意，pos仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：你是否可以使用 O(1) 空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
哈希表
算法思路
借助Set数据结构不能存放重复数据的特性来判断链表是否有环，且记录当前节点，从而可在找到环路之后直接返回入环第一个节点。
编码
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class Solution{
public ListNode detectCycle(ListNode head) {
if(head == null){
return null;
}
Set<ListNode> set = new HashSet<>();
ListNode temp = head;
while(temp != null){
if(!set.add(temp)){
return temp;
}
temp = temp.next;
}
return null;
}
}
复杂度分析
因为整个算法仅使用了一层循环遍历，所以其时间复杂度为O(n)。但是使用了一个HastSet辅助判断是否有重复节点，所以空间复杂度为O(1)。
快慢指针
算法思路
我们也可以借助LeetCode 141题所讲的快慢指针来解答这个道题，首先定义一个快指针（每次走两步），再定义一个慢指针（每次走一步）。如果链表中存在环，慢指针一定会在第一轮与快指针相遇，我们假设环形链表一共有a+b个节点，其中a表示入环口之前的a个节点，b表示形成环的b个节点。
假设快指针和慢指针第一次相遇时，快指针走了f步，慢指针走了s步：
- 因为快指针每次走的步数是慢指针的两部，所以有f=2s；
- 如果快指针要想在环内与慢指针相遇，那么快指针就必须得比慢指针多走n个环的长度，即n*b（b为环内节点个数）;
又假设慢指针在环内走了c步后与快指针相遇，那么这里就有：f = a + nb + c，s = a + c。结合前序条件f=2s，综合三个式子可得：
f = a + c + nb
s = a + c
f = 2s
将s = a + c 和 f = 2s代入f = a + c + nb求得
2s = s + nb => s = nb
再将s = nb代入s = a + c求得
nb = a + c => a = nb - c
最后求得a = nb - c说明从链表起点还是走a步（即入环口），刚好等于环内一圈减去从入环口到相遇点的步数。有了这个结论之后，我们就可以在快慢指针第一次相遇时，将快指针重新指向链表头每次向前走一步，同时慢指针继续按照每次一步向前移动，当他们再次相遇的点，就是入环后的第一个节点。
编码
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class Solution{
public ListNode detectCycle(ListNode head){
if(head == null){
return null;
}
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
fast = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
}
复杂度分析
因为整个算法仅使用了一层循环遍历，所以其时间复杂度为O(n)，并且没有使用任何额外内存空间所以空间复杂度为O(1)。
