Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
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) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if(!head) return NULL; ListNode* one = head; ListNode* two = head; bool isCycle = false; while(two->next && two->next->next) { one = one->next; two = two->next->next; if(one == two) { isCycle = true; break; } } if(isCycle == false) return NULL; one = head; while(one != two) { one = one->next; two = two->next; } return one; } };
