5. Linked List Cycle

Link to the problem

Description

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Example

Input: [1,2,3], tail connects to index 0, output: true
Input: [1, 2, 3], output: false

Idea

Use a slow pointer which advance once each time, a fast pointer which advance once each time.
If the linked list has no cycle, then the fast pointer will reach null.
Otherwise, they never stop, but will meet.

Solution

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return false;
        ListNode *slow = head, *fast = head->next;
        while (fast) {
            if (slow == fast) return true;
            slow = slow->next;
            fast = fast->next;
            if (!fast) return false;
            fast = fast->next;
        }
        return false;
    }
};

Performance

16 / 16 test cases passed.
Runtime: 6 ms