Question
Description
Given a linked list, return the node where the cycle begins.
If there is no cycle, returnnull.
Example
Given-21->10->4->5, tail connects to node index 1，return10
Challenge
Follow up:
Can you solve it without using extra space?
题解思路
可以先判断Linked List是否有Cycle，利用two pointers可以很快得到。接下来就要分析，快慢指针第一次相遇时，位置、步数和环的关系。
a b
A ------ B --------+
| |
c | |
+-------- C
* A: 起始点
* B: Cycle Begins
* C: 1st 快慢指针相遇点
* A->B: a
* B->C: b
* C->B: c
* 环的长度 (b+c) 为 R
第一次相遇时，慢指针所走步数为
a + b
快指针走的步数为
a + b + nR
我们知道快指针是慢指针速度的2倍，因此
2(a + b) = a + b + nR
那么
a + b = nR
同时
b + c = R
所以
a = (n - 1)R + c;
也就是说，从A点和C点同时出发，以相同的速度前进，那么下一次相遇的位置将是B。
参考 LeetCode: https://leetcode.com/articles/linked-list-cycle/
源代码
Easier to understand:
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head;
ListNode fast = head;
while (slow != null && fast != null) {
slow = slow.next;
if (fast.next == null) return null;
fast = fast.next.next;
if (slow == fast) break;
}
slow = head;
if (fast != null) {
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
return null;
}
}
Preferred Implementation:
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
private ListNode answer = null;
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null){
return null;
}
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast == slow) {
slow = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
return null;
}
}
Harder to understand with pointer corner cases
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next==null) {
return null;
}
ListNode fast, slow;
fast = head.next;
slow = head;
while (fast != slow) {
if(fast==null || fast.next==null)
return null;
fast = fast.next.next;
slow = slow.next;
}
while (head != slow.next) {
head = head.next;
slow = slow.next;
}
return head;
}
}