Skip to main content
DSA patterns

Linked List Cycle

easyLinked list Must-doAmazonCiscoMicrosoft

Problem statement

You are given the head of a singly linked list. Each node's next pointer leads to the next node, and a normal list ends when some node's next is null.

Some lists are wired so that a node further down the chain points its next pointer back to a node that came earlier, instead of ending in null. Follow next from that node and you loop forever without ever reaching the end. This is called a cycle.

Return true if the linked list has a cycle, and false if it ends normally.

Think of a chain of config includes: file A includes file B, which includes file C, which includes file A again. Nothing tells you the chain is done — you just keep resolving includes forever unless you check for exactly this kind of loop first.

Examples

Example 1

Input: head = [3,2,0,-4], pos = 1

Output: true

Explanation: The tail node (-4) points back to the node at index 1 (the node holding 2), so following next cycles through 2 → 0 → -4 → 2 → … forever.

Example 1

Example 2

Input: head = [1,2], pos = 0

Output: true

Explanation: The tail node (2) points back to the node at index 0 (the node holding 1), so the two nodes point at each other forever.

Example 2

Example 3

Input: head = [1], pos = -1

Output: false

Explanation: pos = -1 means the single node's next is null — the list ends normally, with no cycle.

Example 3

Hints

Hint 1: One way is to remember every node you have already visited in a set, and check each new node against it. It works, but it costs one slot of memory for every node you see.

Approach

Optimal: Fast & slow pointers

Intuition

Instead of remembering every node, walk the list with two pointers moving at different speeds: slow takes one step at a time, fast takes two. Picture two runners on a track — if the track is a straight line, the faster runner just finishes first. If the track loops back on itself, the faster runner eventually laps the slower one and they end up standing on the same spot.

That's exactly what happens here. If the list has no cycle, fast simply runs off the end (null) before slow does. If the list has a cycle, both pointers eventually enter the loop, and because fast gains one node on slow every step, it cannot skip past slow — it must land on the same node at some point. This beats the hash-set approach because it needs no extra memory at all: just two pointers, regardless of how long the list is.

Steps

  1. Set both slow and fast to head.
  2. While fast and fast.next are not null:
    • Move slow one step: slow = slow.next.
    • Move fast two steps: fast = fast.next.next.
    • If slow and fast are now the same node, return true.
  3. If the loop ends because fast or fast.next became null, the list ran out cleanly — return false.

Dry run

List: N0(3) → N1(2) → N2(0) → N3(-4) → N1 (Example 1)

step slow fast same node?
start N0(3) N0(3) —
1 N1(2) N2(0) no
2 N2(0) N1(2) no
3 N3(-4) N3(-4) yes → return true

Edge cases: an empty list means fast is already null, so the loop body never runs and we return false. A single node with next equal to null fails the fast.next check on the first pass, so we also return false — we never dereference a null pointer.

Complexity

Time O(n) - Without a cycle, the fast pointer reaches `null` after at most n / 2 iterations, so the pass is O(n). With a cycle, once the slow pointer is inside the loop, the fast pointer closes the gap between them by exactly one node every iteration, so they meet within at most one full lap of the cycle — still bounded by the list's length. The extra speed doesn't cost an extra pass.

Space O(1) - Only two pointers are kept no matter how long the list is; the list itself isn't counted as extra space.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def hasCycle(self, head: "ListNode | None") -> bool:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False


def _build_list(values, pos):
    if not values:
        return None
    nodes = [ListNode(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if pos != -1:
        nodes[-1].next = nodes[pos]
    return nodes[0]


if __name__ == "__main__":
    print(str(Solution().hasCycle(_build_list([3, 2, 0, -4], 1))).lower())  # true
    print(str(Solution().hasCycle(_build_list([1, 2], 0))).lower())  # true
    print(str(Solution().hasCycle(_build_list([1], -1))).lower())  # false
RecapThe whole problem in a few lines, for the night before
  • Spot it: "does this linked list ever loop back on itself?" — no length is given up front, and following next might never reach null
  • Idea: walk with two pointers, slow (1 step) and fast (2 steps); if a cycle exists they must land on the same node
  • Cost: O(n) time, O(1) space (the hash-set version: O(n) time, O(n) space)
  • Trap: checking only fast != null before jumping two steps — crashes on a null fast.next when the list has no cycle

Interview follow-ups

  • Return the actual node where the cycle begins, not just whether one exists.

    After slow and fast meet inside the loop, reset one pointer back to head and leave the other at the meeting point. Then move both one step at a time. They are guaranteed to meet again exactly at the first node of the cycle. This works because of the distances involved: the steps from head to the cycle's start equal the steps from the meeting point back around to that same start, once you account for how far fast had already lapped slow. It's still O(n) time and O(1) space — just a second, shorter walk after the first one finds the meeting point.

  • The list is a chain of symlinks resolved by a background worker, and another thread can rewrite a node's next pointer while you are mid-scan. How would you detect a cycle safely?

    The two-pointer trick assumes the structure doesn't change underneath it while it runs, so a concurrent writer breaks that assumption — you could read a next pointer that changes between your two accesses. One option is to take a read lock (or snapshot the chain into an immutable copy) before scanning, which costs the O(n) memory the pointer approach was trying to avoid. Another is to tag each node with a version or generation counter, and if it changes mid-walk, abort and retry the scan rather than trust a possibly-stale result.

Frequently asked questions

The pointer-chasing part is the practice, but the pattern it teaches shows up constantly in infra work: a chain of symlinks that loops back on itself, a config file that includes another file that eventually includes the first one again, or a chain of HTTP redirects that never terminates. Detecting "have I been here before, in constant memory" before you follow a chain blindly is exactly this problem.

If we only checked fast != null, then on a list with an odd number of nodes and no cycle, fast.next would be null on the last useful iteration, and calling fast.next.next would try to read .next off a null reference and crash. Checking fast.next first guarantees there really is a next-next node to jump to.

No. Both approaches compare node references (is this the exact same node object?), never node values. Two different nodes that happen to hold the value 5 are still two different objects, so neither the set nor the pointer comparison would treat them as a repeat. That is exactly why linked-list cycle problems, unlike array duplicate problems, never need to look at .val at all.

This problem only asks for true or false. A very close, and slightly harder, problem (LeetCode 142, Linked List Cycle II) asks you to return the actual node where the loop begins, which needs a second phase of the same two-pointer idea — see the first follow-up below.