剑指offer20_链表中环的入口节点

链表中环的入口节点

---

给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出null。

数据范围

节点 val 值取值范围 $[1,1000]$。

节点 val 值各不相同。 链表长度 $[0,500]$。

样例

给定如上所示的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。则输出环的入口节点3.

---

题解

使用双指针技巧检测链表中是否存在环，并确定环的入口节点。

O(n)线性时间复杂度，每个节点最多被访问两次。

阶段一：检测环是否存在

1. 初始化两个指针：
   • first（慢指针）：每次前进1步
   • second（快指针）：每次前进2步
2. 同时从链表头节点开始移动：
   • 若second遇到nullptr → 链表无环
   • 若first和second相遇 → 链表有环

阶段二：定位环入口

1. 将first移回链表头部
2. second保持在相遇点不动
3. 两指针改为每次各前进1步
4. 当两指针再次相遇时 → 相遇点即为环的入口

数学原理

设：

• 链表头到环入口距离：a
• 环入口到首次相遇点距离：b
• 首次相遇点到环入口距离：c

则有：

1. 首次相遇时：
   • first移动距离：a + b
   • second移动距离：a + b + k*(b + c) （k为绕环圈数）
2. 由速度关系（2倍速）：2(a + b) = a + b + k(b + c)=> a = (k-1)(b + c) + c

---

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *entryNodeOfLoop(ListNode *head) {if(!head || !head->next) return nullptr;auto first = head, second = head;while(first && second){first = first->next;second = second->next;if(second) second = second->next;else return nullptr;if(first == second){first = head;while(first != second){first = first->next;second = second->next;}return first;}}return nullptr;}
};

示例1：有环链表

1 → 2 → 3 → 4↑     ↓6 ← 5

1. 阶段一：
   • slow: 1→2→3→4→5→6
   • fast: 1→3→5→2→4→6
   • 在节点6相遇
2. 阶段二：
   • slow重置到1，fast保持在6
   • slow:1→2
   • fast:6→2
   • 在节点2相遇 → 环入口是2

示例2：无环链表

1 → 2 → 3 → 4 → nullptr

阶段二：

• slow重置到1，fast保持在6
• slow:1→2
• fast:6→2
• 在节点2相遇 → 环入口是2

示例2：无环链表

1 → 2 → 3 → 4 → nullptr

• fast指针会先到达nullptr → 无环