Description Link to heading

142.linked-list-cycle-ii

Solution Link to heading

Like 141.linked-list-cycle, when fast and slow meet each other, we make a pointer p start from virtual head node, traverse one by one, the same as slow. slow and p will meet at the entrance of the cycle.

Code Link to heading 

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *vhead = new ListNode(0, head);
        ListNode *fast = vhead, *slow = vhead;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                while (vhead != slow) {
                    vhead = vhead->next;
                    slow = slow->next;
                }
                delete vhead;
                return slow;
            }
        }
        return nullptr;
    }
};