LeetCode解题报告:Linked List Cycle && Linked List Cycle II

时间:2022-09-14 21:11:18

LeetCode解题报告:Linked List Cycle && Linked List Cycle II

1题目

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

Linked List Cycle II

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

Follow up:

Can you solve it without using extra space?

2思路

2.1 对于判断链表是否有环

用两个指针,一开始都指向头结点,一个是快指针,一次走两步,一个是慢指针,一次只走一步,当两个指针重合时表示存在环了。

证明:假设链表有环,环的长度为N,慢指针在起始位置,快指针在位置k(位置从0开始计数),那么快指针只要比慢指针多走经过N-k步,就可以追上慢指针了。,因为每一次快指针都比慢指针多走一步,所以一定可以在有限的步数追上慢指针。

2.2如何求出环的起始位置

结论:当快指针和慢指针重合的时候,把一个指针重新指向头指针,两个指针现在速度一样,一次走一步,那么当两个指针值相同时,所在的指针就是环的起始位置。

LeetCode解题报告:Linked List Cycle && Linked List Cycle II

证明:假设头指针到环的其实位置的长度是k,环的长度是loop,两个指针相遇的时候,慢指针距离还的起始位置的长度是m。

计算:因为快指针的速度是慢指针的两倍。可以推断出:

distance(快指针) = 2 * distance(慢指针),即

k + loop + m = 2 * ( k + m ) ,化解得出

loop = k + m

分析起始点的位置:通过慢指针继续走loop - m步就可以到达环的起始位置,正好k=loop - m,所以,相遇时把快指针指向头指针,两个指针以相同的速度走k步就可以一起到达环的起始位置了。

可以看看这篇文章的解释,看着像我邮学长的blog

3 代码

public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
boolean hasCycle = false;
while (fast != null && (fast.next != null)) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
hasCycle = true;
break;
}
} // find the start of cycle
if (!hasCycle) {
return null;
}
for (fast = head; fast != slow;) {
fast = fast.next;
slow = slow.next;
}
return fast;
}