题目：
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, returnnull.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;elsepre = pre.next;(2) return slow;
References:
Parallel computing with MATLAB on a cluster requires two products:
