# Linked List

Source: https://www.techinterview.org/post/508845185/linked-list/
Updated: 2026-04-16 · techinterview.org

How does one find a loop in a singly linked list in O(n) time using constant memory? You cannot modify the list in any way (and constant memory means the amount of memory required for the solution cannot be a function of n.).

### Solution

I first figured this out when I was asked the question in a Microsoft interview, so there’s verification that one question in the book was from a real interview. The best part of this problem is that I actually needed to write the code out for it a little while ago to detect a bug.

One way to detect a loop is to iterate over the list with 2 pointers at the same time where one is iterating at double speed. If the 2 pointers are ever equal after they iterate once and before they both reach an end, there’s a loop.

Now for another puzzle.. I think the next question I had to answer was something along the lines of “OK, How do you remove a loop in a linked list with the same constraints?” The latter question definitely seems harder, but in the sequence of questions I’d already answered for the interviewer, the solution was pretty obvious. I’ll leave that solution to someone else today.

Hm. I think I should pick up that book. I’ve always wondered where people got their juicy interview riddles.. I’ve always just repeated ones I’ve heard before or made up new ones along the same lines.

## 2026 Update: Parity Invariants in Modern Software

The Last Ball puzzle demonstrates the power of invariant analysis: identify a property that is preserved through every operation, and you can determine the final state without simulating every step. This technique is directly applicable to algorithm correctness proofs and distributed systems.

**The invariant technique in modern engineering:**

- **Loop invariants** — a property true before and after every iteration, used to prove algorithm correctness (QuickSort, binary search)

- **Transaction invariants** — total balance never changes through valid payment operations

- **Protocol invariants** — Raft consensus guarantees that committed entries are never lost, proven via a leader completeness invariant

**The XOR coding version (asked in 2026):**


```
def final_value(arr):
    """
    Pick any two numbers, remove them, add their XOR back.
    What is the final number?
    Invariant: XOR of all elements never changes.
    """
    result = 0
    for x in arr:
        result ^= x
    return result

print(final_value([3, 5, 7]))  # 3^5^7 = 1, regardless of operation order
```


**Still asked at (2026):** Google (for algorithmic reasoning), Jane Street (for invariant-based proofs), and any role where formal reasoning about system correctness is required.