Code & Fun

第35天。

今天的题目是Linked List Cycle II:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

这道题是判断链表是否有环的升级版。

首先肯定需要fastslow指针来先判断是否有环,如果没有,就直接返回nullptr即可。

然后就是怎么计算出环的入口了。

先来个暴力的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ListNode *detectCycle(ListNode *head) {
vector<ListNode *> lvec;
ListNode *fast = head;
ListNode *slow = head;
while(fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
//lvec.push_back(slow);
if (slow == fast) {
lvec.push_back(slow);
slow = slow->next;
while(slow != fast) {
lvec.push_back(slow);
slow=slow->next;
}
for(auto t:lvec) cout << t->val << endl;
while(find(lvec.begin(),lvec.end(),head) == lvec.end())
head = head->next;
return head;
}
}

return nullptr;
}

当然实际的方法不用那么麻烦:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ListNode *detectCycle(ListNode *head) {
vector<ListNode *> lvec;
ListNode *fast = head;
ListNode *slow = head;
while(fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
slow = head;
while(slow != fast) {
slow = slow->next;
fast = fast->next;
}
return fast;
}
}

return nullptr;
}

emmmm,一直很好奇为什么可以这样判断,就去搜了一下,发现了这个判断单向链表是否有环及求环入口的算法数学证明.


本文首发于Code & Fun