How to Determine Linked List Cycle in C/C++?

Question: How to determine if a linked list has a cycle? The Singly Linked List is defined as follows:

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

Using O(n) Hashset

With hashset, this becomes straightforward to store the visited nodes:

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> visited;
        if (head == NULL) {
            return false;
        }
        while (head) {
            if (visited.count(head)) {
                return true; // has appeared before
            }
            visited.insert(head);
            head = head->next;
        }
        return false;
    }
};

Hashset/Hashmap normally has O(n) space complexity.

Fast and Slow Pointers

The O(1) space complexity solution uses two pointers: fast and slow. The fast pointer always advances every two nodes while the slow pointer advances one node at a time. If they somehow meet in the middle, we have a loop.

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

This approaches work because given any length cycle, starting same node, two pointers will meet eventually.

–EOF (The Ultimate Computing & Technology Blog) —