Again, a classic interview question of linked list. Similar to Linked List Cycle, we maintain two pointers fast and slow: fast move two steps at one time while slow moves one step at a time. Once they become NULL, return NULL (no cycle). Otherwise, they will equal at some time. At this time, move any one of them back to head and then move both of them one step at a time. Then they will meet at the same node again. At this time, that node is where the cycle begins. Return it and we are done.
The code is as follows.
1 ListNode* detectCycle(ListNode* head) { 2 ListNode* slow = head; 3 ListNode* fast = head; 4 while (fast && fast -> next) { 5 slow = slow -> next; 6 fast = fast -> next -> next; 7 if (slow == fast) { 8 slow = head; 9 while (slow != fast) { 10 slow = slow -> next; 11 fast = fast -> next; 12 } 13 return slow; 14 } 15 } 16 return NULL; 17 }
