第二周主题：链表 之 Linked List Cycle in LeetCode (in java)

题目：

http://oj.leetcode.com/problems/linked-list-cycle/

http://oj.leetcode.com/problems/linked-list-cycle-ii/



要求：
I Given a linked list, determine if it has a cycle in it.


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?

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */


(给定一个ListNode结构的链表，(I)看是否有cycle；(II)看循环在哪个节点，如果没有cycle，返回null)




解答：




(I) 设定两个index node: slow and fast，沿着链表的顺序跑下去：slow跑得慢，每次跑一步；fast跑得快，每次跑两步。如果有cycle的话，迟早两个index是会相遇的。




(0) ListNode slow = head; ListNode fast = head;

(1) while (true) 循环内slow = slow.next; fast = fast.next.next; (注意先判断fast.next是否为null)

fast.next == null -> return false;
slow == null -> return false;
fast == null -> return false;
slow == fast -> return true;





(II) 假设找到了cycle (slow == fast)，怎么找是哪个节点开始呢？我们引入一个ListNode pre = head; pre每次跑一步，slow循环一圈找是否slow == pre。那怎么判断slow是否循环一圈呢？别忘了，我们的fast还在那呢，保持fast不动，只要看是否slow == fast就知道了。

(0) slow == fast is true

(1) while (pre != slow) 循环内 slow = slow.next;

slow跑圈 


while ((slow != pre) && (slow != fast)) {
 slow = slow.next;
}

 如果slow跑完了，或者遇到pre了



if (slow == pre)

break;

else

pre = pre.next;




(2) return slow;

References:

[1] 代码在
https://github.com/RockyNiu/LeetCode/blob/master/src/leetcode/java/LinkedListCycle.java
https://github.com/RockyNiu/LeetCode/blob/master/src/leetcode/java/LinkedListCycleII.java