Remove Loop in Linked List

Remove Loop in Linked List takes the classic cycle-detection trick one step further. It is not enough to know a loop exists — we have to find exactly where it starts and snip the single back-edge that closes it, turning a tangled list back into a clean, terminating chain.

The slow way first

The obvious idea: walk the list and remember every node you have visited in a hash set. The moment you step onto a node you have already seen, you have found the start of the loop — and the previous node is the tail whose next you must clear. That works, but it costs O(n) extra space for the set.

The question to ask: can I find the loop start using only a couple of pointers? Yes. Floyd’s tortoise-and-hare detects the loop in O(1) space, and a small follow-up walk pinpoints exactly where the loop begins.

The idea: detect, then locate, then cut

Use two pointers. slow advances one node per step; fast advances two. If there is a loop, fast eventually laps slow and they land on the same node inside the loop. That meeting point is not the loop start — but here is the magic: reset slow to the head and advance both pointers one step at a time. They are guaranteed to meet again exactly at the loop start. Finally, walk one pointer around the loop until its next is the loop start; that node is the tail, so set its next = None.

The reason resetting works comes from the geometry: the distance from the head to the loop start equals the distance from the meeting point to the loop start (measured around the loop). So two pointers moving at the same speed from those two places arrive together at the start.

Walk through it

Step through the animation. In phase 1, slow and fast race until they collide on node 4 inside the loop. In phase 2, slow jumps back to the head while fast stays put, and both advance one node per step until they meet at node 3 — the loop start. In phase 3, fast walks on until fast.next is node 3, landing on node 6, and we clear node 6’s next to delete the back-edge.

Pseudocode

slow = fast = head
move slow by 1 and fast by 2 until they meet (or fast falls off the end)
if fast fell off the end: there is no loop, return head
slow = head
move slow and fast each by 1 until slow == fast   # this is the loop start
move fast around the loop until fast.next == slow  # fast is now the tail
fast.next = None                                    # cut the back-edge
return head

The Python solution

def remove_loop(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return head            # no loop
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    while fast.next is not slow:
        fast = fast.next
    fast.next = None           # drop the back-edge
    return head

• slow = fast = head parks both pointers at the head to begin phase 1.
• The first while is the detection loop: slow moves one node, fast moves two. If they ever land on the same node (slow is fast), we break — a loop exists.
• The while ... else is a Python trick: the else runs only if the loop finished without breaking, meaning fast reached None. That means no loop, so we return the head untouched.
• slow = head starts phase 2. We then step slow and fast one node at a time until slow is fast; that shared node is the loop start.
• The last while is phase 3: advance fast around the loop until fast.next is the loop start. Now fast is the tail node whose pointer closes the loop.
• fast.next = None cuts the back-edge, and the list now terminates cleanly.

Complexity

Both approaches are linear time, but Floyd does it with only two pointers — no auxiliary structure — so it wins on space. That O(1)-space cycle handling is exactly why interviewers love this pattern.

When this pattern shows up

Practice