Floyd 判环后，从头和相遇点各走一步，第二次相遇即入环点。
OJ: leetcodecn
题目 ID: linked-list-cycle-ii
难度:普及+/提高
标签:链表双指针哈希表cpppython
日期: 2026-07-28 22:05
题意
返回链表开始入环的第一个节点。无环返回 nullptr。
思路
快慢指针相遇后，慢指针从头重新走，快指针从相遇点继续走（每次一步），再次相遇处即入环节点。
数学推导：设环前长度 a，环长 b，相遇时 slow 走了 a + x，fast 走了 a + x + kb。由 2(a+x) = a+x+kb 得 a = (k-1)b + (b-x)，所以从头和相遇点同步走一定在入环点相遇。
代码
cpp
/**
* Author by Rainboy
*/
// main.cpp：相遇后从头和相遇点各走一步，第二次相遇即入环点。
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
auto slow = head, fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return nullptr;
}
};
ListNode *build(istream &in, int n) {
if (!n)
return nullptr;
auto head = new ListNode(0), cur = head;
for (int i = 0, v; i < n; i++) {
in >> v;
cur->next = new ListNode(v);
cur = cur->next;
}
return head->next;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
auto head = build(cin, n);
auto ans = Solution().detectCycle(head);
cout << (ans ? ans->val : -1) << '\n';
return 0;
}python
#!/usr/bin/env python3
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
return None
def build(arr):
dummy = cur = ListNode(0)
for v in arr:
cur.next = ListNode(v)
cur = cur.next
return dummy.next
def main() -> None:
n = int(input())
a = list(map(int, input().split()))
head = build(a)
ans = Solution().detectCycle(head)
print(ans.val if ans else -1)
if __name__ == "__main__":
main()复杂度
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
总结
Floyd 判环的进阶版，利用距离关系找到环的入口。