141. Linked List Cycle

解題思路

slow/fast pointer 可以用來判斷 linked list 是否有環狀結構。因為 fast pointer traverse 的速度是 slow pointer 的兩倍，因此如果有環，兩個 pointer 一定會在繞圈圈的某次相遇。反之若無環，那當 fast 走到尾端就結束。

程式碼

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr)
            return false;

        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
                return true;
        }
        return false;
    }
};