My code:
/**
* 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)
return null;
boolean hasCycle = false;
ListNode tortoise = head;
ListNode rabbit = head.next;
while (rabbit != null) {
if (rabbit == tortoise) {
hasCycle = true;
break;
}
rabbit = rabbit.next;
if (rabbit == null) {
hasCycle = false;
break;
}
rabbit = rabbit.next;
tortoise = tortoise.next;
}
if (rabbit == null)
hasCycle = false;
if (!hasCycle)
return null;
ListNode tortoise2 = head;
rabbit = rabbit.next;
while (tortoise2 != rabbit) {
tortoise2 = tortoise2.next;
rabbit = rabbit.next;
}
return rabbit;
}
}
My test result:
Paste_Image.png
这是一道数学题。
具体，请看这篇博客的解释。
http://bangbingsyb.blogspot.com/2014/11/leetcode-linked-list-cycle-i-ii.html
然后具体再自己画一下，移动步数那一块儿代码写起来有些细节，如果直接画一画，就很容易过了。
**
总结： 双指针， 数学， List
**
Anyway, Good luck, Richardo!
My code:
/**
* 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;
boolean hasCycle = false;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next;
fast = fast.next;
if (fast == slow) {
hasCycle = true;
break;
}
}
if (!hasCycle)
return null;
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
看了数学推理，知道了怎么做，写出了答案。
我自己没有推出来。忘记了一个关键点。快指针，走的路程是慢指针的两倍。
假设头结点到环开始处的距离是L, 环开始处，到两个人碰到的地方，距离是X
那么，
2 * (L + X) = L + n * C + X => L = n*C - X
n * C - X 物理意义是，相遇处到环开始处的距离。
也就是说，把慢指针放回到起点。让快慢指针同时一步一步走。下一次相遇的地方，就是环开始的地方。
妙啊。 Fuck, 浪费时间！
Anyway, Good luck, Richardo!
My code:
/**
* 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 (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast.next == null || fast.next.next == null) {
return null;
}
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
差不多的做法，数学推导。
Anyway, Good luck, Richardo! -- 08/15/2016
