LeetCode 141. Linked List Cycle [Easy] [C++] 解題筆記

這題給我們一個 Linked List 要我們判斷該 Linked List 有沒有包含環 (cycle)。

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

想法:

    單純判斷有沒有 cycle 的話只需要利用 Two pointers 快慢指針的技巧就可以簡單判斷，宣告兩個指針 fast 與

slow，讓 fast 每次兩個 nodes 而 slow 走一個，只要 fast 與 slow 相遇就表示 linked list 含有 cycle。

完整程式碼:

/* 用兩個指標賽跑,讓一個跑比較快一個比較慢
 * 如果有cycle則跑得快的終究會追上慢的
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL) { return false; }
        auto slow = head;
        auto fast = head->next;
        while (slow != NULL && fast != NULL && fast->next != NULL) {
            if (slow == fast) {
                return true;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return false;
    }
};