Linked List Cycle II 103
Question
Given a linked list, return the node where the cycle begins.
If there is no cycle, return null.
Example
Given -21->10->4->5, tail connects to node index 1,return 10
Challenge
Follow up:
Can you solve it without using extra space?
Solution
先用快慢指针判断是不是存在环
当slow和fast第一次相遇时,将slow放回Start处,fast向下移动一步,两个指针再一起移动,直到再次相遇,就是交点
为什么slow放回start处,fast要向下移动一位:slow和fast第一次相当于从head之前的一个dummy node一起出发,slow移动一步到head,fast移动两步到head.next,所以第一次相遇之后,相当于要将slow放回dummy,然后slow和fast一起移动(一步之后slow到达head,fast到达fast.next)。
证明:
现在有两个指针,第一个指针,每走一次走一步,第二个指针每走一次走两步,如果他们走了t次之后相遇在K点
那么指针一走的路是 t = X + nY + K ①
指针二走的路是 2t = X + mY+ K ② m,n为未知数
把等式一代入到等式二中, 有
2X + 2nY + 2K = X + mY+ K
X + (2n-m)Y + K = 0;
X + K = (m - 2n)Y
这就清晰了,X和K的关系是基于Y互补的。等于说,两个指针相遇以后,再往下走X步就回到Cycle的起点了。
代码如下:
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The first node of linked list.
* @return: The node where the cycle begins.
* if there is no cycle, return null
*/
public ListNode detectCycle(ListNode head) {
// write your code here
if(head == null || head.next == null){
return null;
}
ListNode slow = head;
ListNode fast = head.next;
while(slow != fast){
if(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}else{
return null;
}
}
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}