Linked List Cycle Detection

Problem

Given the beginning of a linked list head, return true if there is a cycle in the linked list. Otherwise, return false.

There is a cycle in a linked list if at least one node in the list can be visited again by following the next pointer.

Internally, index determines the index of the beginning of the cycle, if it exists. The tail node of the list will set it’s next pointer to the index-th node. If index = -1, then the tail node points to null and no cycle exists.

Note: index is not given to you as a parameter

Examples

Example 1:

Input: head = [1,2,3,4], index = 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], index = -1

Output: false

Constraints

• 0 <= Length of the list <= 1000.
• -1000 <= Node.val <= 1000
• index is -1 or a valid index in the linked list.

You should aim for a solution with O(n) time and O(1) space, where n is the length of the given list.

Solution

Walk the linked list, store addresses we’ve seen, and check for duplicates

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 
class Solution {
public:
    bool hasCycle(ListNode* head) {
        // Empty list has no cycle
        if (!head) {
            return false;
        }
        // Walk the linked list, store addresses we've seen
        // If we come across a duplicate, then cycle found
        std::unordered_set<ListNode*> seen;
        while (head) {
            if (seen.contains(head)) {
                return true;
            }
            // Store seen node and walk to next link
            seen.insert(head);
            head = head->next;
        }
        return false;
    }
};