Linked Lists: The Core Idea

Picture a treasure hunt. Each clue tells you where the next clue is hidden. To reach clue 7 you must read clues 1 to 6 in order; there is no shortcut. And if you throw a clue away before reading where it points, the rest of the hunt is lost for good.

A singly linked list is that treasure hunt. Each node holds a value and the address of the next node, and nothing else. There is no index and no length. You hold the first node — the head — and reach everything else by following next, one step at a time.

Interview problems on linked lists are almost never about computing something clever. They are about pointer surgery: changing which node points at which, in place, without dropping any part of the chain. The skill being graded is care — saving what you are about to overwrite, and handling the first and last node without crashing.

The node

Every lesson in this section uses the same node class.

1class ListNode:2    """One node of a singly linked list."""34    def __init__(self, value: int = 0, next_node: "ListNode | None" = None) -> None:5        self.value = value6        self.next = next_node       # the ONLY link: a node knows its successor, nothing else

A list 1 → 2 → 3 is three nodes: the first has next pointing at the second, the second at the third, and the third at None. An empty list is simply head = None.

How to recognise it

1. The input is a chain of nodes. The signature says head: ListNode. That alone puts you in this section or in Fast and Slow Pointers.
2. The verb is structural. Reverse, merge, remove, insert, reorder, rotate, partition, swap. You are changing the shape of the chain, not computing a number from it.
3. "O(1) extra space" or "modify the list in place". Copying the values into an array, solving there and rebuilding is a legal answer, but it costs O(n) space and skips the skill being tested. When the problem forbids it, you must do the surgery on the nodes.
4. Position counted from the end. "The n-th node from the end." An array answers this with arithmetic. A list has no length and no random access, so it needs a pointer trick.

Constraints for list problems are usually small (often at most 10⁴ or 10⁵ nodes), and almost every solution is O(n) time. So the constraints do not tell you which technique to use. The space requirement does: O(1) extra space means in-place pointer work.

How it works

An array stores its elements in one continuous block of memory. Element i lives at start + i × size, so reading element 1,000 is one multiplication and one memory read. A linked list allocates each node separately, wherever there is room. Reaching node 1,000 means reading 999 nodes first, one address at a time — and because the addresses are scattered, each read is likely to miss the CPU cache.

The list wins in exactly one row: inserting or deleting where you are already standing. To delete B from A → B → C you need a reference to A, and then it is one assignment:

previous.next = previous.next.next     # A now points at C; B is unreachable

No shifting. An array would move every later element back one slot. That one row is the reason linked lists exist, and why every problem here hands you node references rather than indices. In production code arrays usually win on speed thanks to cache locality; linked lists survive in interviews because they test careful pointer work with no safety net.

The techniques

Almost every linked-list problem is built from four techniques.

Harder problems are usually two or three of these in sequence. Reorder List, for example, is find-the-middle, then reverse, then merge. Recognising the pieces is most of the work.

The templates

Traversal. Visit every node once.

1node = head2while node is not None:3    # use node.value here4    node = node.next

Removing with a dummy head. Delete every node holding target.

1def remove_elements(head: ListNode | None, target: int) -> ListNode | None:2    """Delete every node holding target. The dummy gives the head a predecessor."""3    dummy = ListNode(0, head)4    previous = dummy5    while previous.next is not None:6        if previous.next.value == target:7            previous.next = previous.next.next   # unlink; do NOT advance8        else:9            previous = previous.next10    return dummy.next

Deleting a node needs its predecessor, and the real head has none. Without a dummy you need a separate loop to strip matching nodes off the front and a guard for the list becoming empty. With a dummy, the head is just another node whose predecessor happens to be dummy. The function returns dummy.next, which is the real head whether or not it changed.

Trace it on 7 → 7 → 3, target 7:

The head changed twice and no line of code had to notice. On an empty list the loop never runs and dummy.next is None, which is correct.

Building a new list with a dummy and a tail.

1dummy = ListNode()2tail = dummy3for value in values:4    tail.next = ListNode(value)5    tail = tail.next6return dummy.next

The first append writes to dummy.next, every later one to a real node — the same line either way. Merge Two Sorted Lists and Add Two Numbers are this shape.

Reversal. Four lines in a fixed order: save the successor, flip the pointer, advance previous, advance current. The next lesson, Reverse Linked List, takes it apart line by line.

Complexity

Nearly every linked-list solution is O(n) time: each node is visited a constant number of times. The interesting number is space.

• Pointer surgery with a few variables is O(1) extra space, however long the list is. A dummy node is one node, so it is O(1) too.
• Copying values or nodes into an array is O(n) extra space.
• Recursion is O(n) space as well, because each call waits on the stack. CPython stops at about 1,000 nested calls by default, so a recursive solution crashes on a 5,000-node list — we ran it, and it raised RecursionError.
• Building a new list (as in Add Two Numbers) needs O(n) space for the output. That is not counted as "extra" space, but say it.

Where it goes wrong

1. Losing the rest of the list. Writing current.next = previous before saving current.next destroys the only reference to the remaining nodes. The result is a list of one or two nodes. It looks like an off-by-one; it is not. Save before you overwrite.

2. Stepping past the end. node.next.value crashes when node is the last node, and fast.next.next crashes when fast.next is None. Check from left to right and stop at the first None: while fast is not None and fast.next is not None. Python's and stops early, so fast.next is never read when fast is None. Swap the two clauses and it crashes.

3. Forgetting to cut. When you split a list or move its tail, the old last node may still point into the other part. Reorder List without slow.next = None, or a recursive reversal without head.next = None, builds a cycle. A cycle raises no error: the next traversal simply runs forever, and the judge reports a timeout. A linked-list solution that times out is almost always a cycle, not a slow algorithm.

4. Returning the wrong node. Reversal returns previous, not current (which is None at the end). A function with a dummy head returns dummy.next, not dummy — returning dummy puts an extra 0 on the front. A merge returns dummy.next, not tail.