Linked Lists

An array gives you random access; a linked list gives you a treasure hunt. Each node holds a value and a single pointer to the next node:

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

The defining danger: once you overwrite a next pointer, everything it pointed to is unreachable unless you saved a reference first. This is why linked-list bugs feel like surgery gone wrong — you clamped the wrong artery.

The discipline that prevents it is almost embarrassingly low-tech: draw the boxes and arrows before writing a line of code. Three nodes, an arrow per pointer, then physically redraw the arrows in the order your code will move them. If a node ever has zero arrows pointing at it mid-diagram and you still need it — you just found the bug before the interviewer did.

# Splicing out node b from a -> b -> c
a.next = b.next   # a -> c; b still points at c but nothing points at b

One line, but only safe because we read b.next before anyone overwrote it. Order of operations is everything.

Half of linked-list edge-case bugs share one root cause: the head has no predecessor, so any operation that needs "the node before X" breaks when X is the head.

The fix is to manufacture a predecessor. Allocate one throwaway node, point it at the head, and suddenly every real node has something before it:

dummy = ListNode(0, head)
prev = dummy
while prev.next:
    if should_remove(prev.next):
        prev.next = prev.next.next   # works even when removing the head
    else:
        prev = prev.next
return dummy.next                    # the possibly-new head

No if node is head branch, no separate code path. The dummy head is the linked-list version of a sentinel value: spend O(1) memory to delete an entire class of conditionals. Use it any time the head itself might be modified, removed, or merged — which is most of the time.

You can't index into a linked list, but you can walk it at two speeds — and the relationship between two walkers answers questions that look like they'd need extra memory.

Find the middle: advance slow one step and fast two. When fast runs off the end, slow stands at the midpoint.

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow is the middle (second middle for even length)

Detect a cycle (Floyd's algorithm): if the list loops, the fast walker enters the loop first and then laps the slow one — on a circular track, a runner going 2× must catch a runner going 1×. They meet inside the cycle; if instead fast hits None, the list is a straight line.

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow is fast:
        return True      # lapped — there's a cycle
return False

Note is, not ==: we're asking whether they're the same node, not nodes with equal values. The same two-walker idea, offset instead of doubled, finds the n-th node from the end in one pass.

If linked lists have one move you must be able to write cold, half-asleep, on a whiteboard, it's in-place reversal. It shows up alone, and it hides inside harder problems (palindrome check, reorder list, reverse-in-k-groups).

The loop maintains exactly two regions: a reversed prefix behind prev, and the untouched rest ahead of cur. Each iteration moves one node across the frontier:

prev, cur = None, head
while cur:
    nxt = cur.next      # 1. save the rest before you cut it loose
    cur.next = prev     # 2. flip one arrow
    prev = cur          # 3. advance the reversed region
    cur = nxt           # 4. step into the saved rest
return prev             # new head

Four lines, in that exact order — step 1 before step 2 is the whole game, because flipping the arrow first would orphan the rest of the list. Say the invariant out loud in the interview: "everything behind prev is reversed, everything from cur on is untouched." Invariants stated clearly are how you debug pointer code without running it — and how interviewers tell the trained from the lucky.