142. 环形链表 II
题目描述
输入单链表的头节点 head。如果链表有环，返回环的第一个节点，即从头节点沿 next 前进时最先进入环的那个节点；如果没有环，返回空。要返回的是节点本身，而不是值。
测试数据用数组给出节点值，并用整数 pos 说明尾节点连到哪个下标（从 0 开始），pos = -1 表示无环。pos 不会传给函数。
展示结果时，输出返回节点在链表中的下标；返回空时输出 -1。不允许修改链表。
示例 1
输入：head = [3,2,0,-4], pos = 1 输出：1
解释：尾节点连到下标 1，环从下标 1 的节点开始。
示例 2
输入：head = [1,2], pos = 0 输出：0
解释：尾节点连回头节点，入环点是下标 0。
示例 3
输入：head = [1], pos = -1 输出：-1
解释：无环，返回空，展示为 -1。
数据范围
- 节点数在
[0, 10^4]之间。 -10^5 <= Node.val <= 10^5pos为-1，或是链表中合法的下标。
进阶：能否只用 O(1) 的额外空间找到入环点？
解题思路：快慢指针
快指针每次走两步，慢指针走一步；相遇后另设指针从头出发，两者同步走到入口。
为什么正确
相遇后，头到入口的距离与相遇点绕环到入口的距离模环长相同。
复杂度分析
时间 O(n)，额外空间 O(1)。
易错点
不要返回第一次相遇点；节点值相等不代表是同一节点。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def detectCycle(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
p = head
while p is not slow:
p = p.next
slow = slow.next
return p
return Noneclass Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode p = head;
while (p != slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
return null;
}
}class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode *p = head;
while (p != slow) {
p = p->next;
slow = slow->next;
}
return p;
}
}
return nullptr;
}
};func detectCycle(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
p := head
for p != slow {
p = p.Next
slow = slow.Next
}
return p
}
}
return nil
}var detectCycle = function(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let p = head;
while (p !== slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
return null;
};function detectCycle(head: ListNode | null): ListNode | null {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) {
let p = head;
while (p !== slow) {
p = p!.next;
slow = slow!.next;
}
return p;
}
}
return null;
}其他解法
哈希法直观但要 O(n) 空间；快慢指针利用相遇点到入口的距离关系，只用 O(1) 空间。
解法 2：哈希集合 时间 O(n)，空间 O(n)
顺着 next 遍历链表，把访问过的节点放入哈希集合。第一个重复遇到的节点就是入环点。若走到空指针，说明无环。
不需要推导距离关系，正确性一目了然。需要 O(n) 额外空间。
class Solution:
def detectCycle(self, head):
seen = set()
while head:
if head in seen:
return head
seen.add(head)
head = head.next
return Noneclass Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> seen = new HashSet<>();
while (head != null) {
if (!seen.add(head)) return head;
head = head.next;
}
return null;
}
}class Solution {
public:
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode*> seen;
while (head) {
if (!seen.insert(head).second) return head;
head = head->next;
}
return nullptr;
}
};func detectCycle(head *ListNode) *ListNode {
seen := map[*ListNode]bool{}
for head != nil {
if seen[head] {
return head
}
seen[head] = true
head = head.Next
}
return nil
}var detectCycle = function(head) {
const seen = new Set();
while (head) {
if (seen.has(head)) return head;
seen.add(head);
head = head.next;
}
return null;
};function detectCycle(head: ListNode | null): ListNode | null {
const seen = new Set<ListNode>();
while (head) {
if (seen.has(head)) return head;
seen.add(head);
head = head.next;
}
return null;
}