Coding interview problems › Linked Lists

🔗 Linked Lists Medium

Linked List Cycle II (Find Where the Cycle Starts)

Find the node where a linked list cycle begins: after Floyd's pointers meet, reset one to the head and step both together. Proof, tested Python, live visual.

Also searched as: find start of loop in linked list · Floyd's algorithm cycle start · detect and remove loop in linked list

🔗

Try it live Free

Linked Lists: Reverse & Floyd's Cycle

Turn on a cycle in the linked list lab and watch where the tortoise and hare meet; that meeting point is the starting place for the second, one-step-at-a-time walk.

Open the playground →

The problem

Given the head of a singly linked list, return the node where a cycle begins, or None if there is no cycle. Do not modify the list, and aim for O(1) extra memory.

Input3 -> 2 -> 0 -> 4, and 4 points back to 2
Outputthe node with value 2
Input1 -> 2 -> None
OutputNone

The key insight

First detect the cycle with Floyd's slow and fast pointers. Then the neat part: if the head is a steps from the cycle start, the meeting point is also a steps (plus whole laps) before the start, going forward round the loop. So reset one pointer to the head, move both one step at a time, and they meet exactly at the cycle's first node.

Brute force first: Walk the list storing each node in a set; the first node you see twice is the start. That is O(n) time but O(n) space.

Step-by-step approach

  1. Run Floyd's algorithm: slow moves 1 step, fast moves 2, until they meet or fast runs out.
  2. If fast reaches the end, return None.
  3. Set a pointer p = head and keep slow at the meeting point.
  4. Advance p and slow one step at a time until they are the same node.
  5. Return that node: it is the start of the cycle.

Python solution

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


def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                    # inside the cycle
            p = head
            while p is not slow:            # both are a steps from the start
                p, slow = p.next, slow.next
            return p
    return None

Complexity

TimeO(n)
SpaceO(1)

Phase one takes at most O(n) moves to meet, and phase two at most the distance from the head to the cycle, also O(n). Only a few pointers are used.

Common mistakes

Frequently asked questions

What is the time and space complexity?

O(n) time and O(1) extra space.

Why does resetting one pointer to the head work?

Let a be the distance from head to the cycle start, b the distance from the start to the meeting point, and c the cycle length. The fast pointer travelled twice as far as the slow one, which gives a = k·c - b for some whole number k, so walking a steps from the meeting point lands on the cycle start.

How do I remove the cycle once I find the start?

Walk from the start node around the loop until you reach the node whose next is the start, then set that node's next to None.

How do I find the length of the cycle?

From the meeting point, keep moving one pointer until it comes back to the same node, counting steps. That count is the cycle length.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Linked Lists Linked Lists: Reverse & Floyd's Cycle lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.