141. Linked List Cycle - Leetcode Solution

LeetCode problem

Solution code

💡 Step-by-Step Thought Process

Understand the problem: Determine if a linked list has a cycle, where a cycle means a node’s next pointer points to a previously visited node.
Initialize two pointers, slow and fast, both starting at the head of the list.
While fast and fast.next are not None, move fast two steps (fast.next.next) and slow one step (slow.next).
Check if slow equals fast (same node); if true, a cycle exists, so return True.
If fast or fast.next becomes None, the list ends, so return False.

Code Solution

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

            if slow is fast:
                return True

        return False

# Time Complexity: O(n)
# Space Complexity: O(1)

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode dummy;
        dummy.next = head;
        ListNode *slow = &dummy, *fast = &dummy;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {
                return true;
            }
        }

        return false;
    }
};

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy, fast = dummy;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                return true;
            }
        }

        return false;
    }
}

var hasCycle = function(head) {
    const dummy = new ListNode(0);
    dummy.next = head;
    let slow = dummy, fast = dummy;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            return true;
        }
    }

    return false;
};

Detailed Explanation

Understanding the Problem: Linked List Cycle

The “Linked List Cycle” problem asks us to determine whether a given singly linked list contains a cycle. A cycle occurs when a node's next pointer points to a previously visited node, causing the list to loop indefinitely.

Example:

Input: A list where the last node links back to an earlier node
Output: true
Input: A list where the last node points to null
Output: false

Why This Problem Matters

Detecting cycles in a linked list is a foundational algorithm in computer science and has practical applications in memory management, graph traversal, and detecting infinite loops. This problem is also a great introduction to the two-pointer (tortoise and hare) technique.

Optimal Approach: Floyd’s Tortoise and Hare Algorithm

The most efficient method to detect a cycle in a linked list is to use two pointers:

Slow Pointer: Moves one node at a time.
Fast Pointer: Moves two nodes at a time.

If a cycle exists, the fast pointer will eventually “lap” the slow pointer — they will meet at some point. If there is no cycle, the fast pointer will reach the end of the list.

Steps:

Initialize both slow and fast pointers at the head of the list.
While fast and fast.next are not null:
- Move slow one step forward (slow = slow.next).
- Move fast two steps forward (fast = fast.next.next).
- If slow === fast, a cycle exists — return true.
If the loop ends without meeting, return false.

Example Walkthrough

Input: 3 → 2 → 0 → -4, with -4 pointing back to 2
Execution:

slow = 3, fast = 3
slow = 2, fast = 0
slow = 0, fast = 2
slow = -4, fast = -4 → match found → return true

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes. In the worst case, fast pointer visits each node at most twice.
Space Complexity: O(1), as no additional data structures are used.

Edge Cases to Consider

Empty list → return false
Single node with no cycle → return false
Single node that points to itself → return true

Conclusion

The “Linked List Cycle” problem is a classic use of the two-pointer technique. It shows how clever pointer manipulation can solve problems efficiently without the need for additional memory. Mastering this approach will prepare you for more advanced problems involving cycles and fast-slow pointer techniques in graphs and linked lists.

NEW!Need help landing software roles? 💡

AlgoMap.io