【Leetcode】142.环形链表-ii（快慢指针）

/*
 * @lc app=leetcode.cn id=142 lang=cpp
 *
 * [142] 环形链表 II
 * 
 * 思路：快慢指针法，快指针一次走2步，慢指针一次走1步。
 * 如果快指针遇见NULL，表示无循环，否则总会相遇，这个时候，快指针的路是慢指针的2倍。
 * 然后一个指针从慢指针开始，一个指针从开头开始，步长均为1，
 * 因为上一步相遇的位置快指针的路是慢指针的2倍，所以这么走下去两个指针一定会在同样的位置相遇。
 * 既然会在同一位置相遇，且步长都为1，所以两者在进入循环结点的时候就一定相遇了。
 * 这样就可以找到循环结点的位置啦。
 * 
 */

// @lc code=start
/**
 * 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) {
        // 建一个辅助头结点
        ListNode *root = new ListNode(-1);
        root->next = head;
        ListNode *slow = root;
        ListNode *fast = root;
        bool meet = false;
        while(fast->next != NULL && fast->next->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            // 相遇
            if (fast == slow)
            {
                meet = true;
                break;
            }
        }
        delete(root);
        // 如果没有相遇
        if (!meet)
            return NULL;
        // 重新再跑一遍，一个从开始出发，一个从慢指针的位置出发，步长都为1
        ListNode *start = head;
        slow = slow->next;
        while (start != slow)
        {
            start = start->next;
            slow = slow->next;
        }
        return start;
    }
};