## Sunday, November 16, 2014

### [LeetCode] Linked List Cycle I, II

Given a linked list, determine if it has a cycle in it.
Can you solve it without using extra space?
Given a linked list, return the node where the cycle begins. If there is no cycle, return `null`.
Can you solve it without using extra space?

2. 如果有环，如何判断环的起始点。

(L + X)*2 = L + n*C + X => L = n*C - X

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20``` ```class Solution { public: ListNode *detectCycle(ListNode *head) { if(!head) return NULL; ListNode *slow = head, *fast = head; do { if(!fast->next || !fast->next->next) return NULL; fast = fast->next->next; slow = slow->next; } while(slow!=fast); slow = head; while(slow!=fast) { slow = slow->next; fast = fast->next; } return slow; } }; ```

fast每次移动的时候要判断是否遇到尾部，如遇到则说明无环。而slow不需要判断。

#### 1 comment:

1. Programming is very interesting and creative thing if you do it with love. Your blog code helps a lot to beginners to learn programming from basic to advance level. I really love this blog because I learn a lot from here and this process is still continuing.
Love from Pro Programmer