题目描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
说明：不允许修改给定的链表。进阶：你是否可以不用额外空间解决此题
题解
仍然使用双指针的方法，关键点是：
- 走a+nb步一定是在环入口
- 第一次相遇时慢指针已经走了nb步
第一次相遇，快慢指针必然都走过a步进入环中，在环中相遇。 f = 2s 且 f=s+nb，因此 s=nb , f=2nb，即第一次相遇时，fast和slow 指针分别走了 2n，n 个 环的周长。慢指针在环中已经走了nb，再让它走a步就到了入口节点了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| ListNode *detectCycle(ListNode *head) {
if (!head || !head->next)return nullptr;
ListNode *t1 = head, *t2 = head;
do
{
t1 = t1->next;
t2 = t2->next;
if (t2)
t2 = t2->next;
else
return nullptr;
} while (t1 && t2&&t1 != t2);
if (!t2)return nullptr;
ListNode* tmp = head;
while (tmp != t1)
{
tmp = tmp->next;
t1 = t1->next;
}
return tmp;
}
|
真是失败啊。所以要学着改变了呢。