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如何求出环的起始位置
结论:当快指针和慢指针重合的时候,把一个指针重新指向头指针,两个指针现在速度一样,一次走一步,那么当两个指针值相同时,所在的指针就是环的起始位置。
证明:假设头指针到环的其实位置的长度是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;
}