Linked Lists

TL;DR: A linked list is nodes chained by next pointers, so you splice in or out in O(1) once you hold the right pointer, but you pay O(n) to reach an index and you lose cache locality. The three patterns interviewers actually test are the dummy head (so deleting or inserting at the front needs no special case), fast/slow pointers (cycle detection and midpoint in one pass, O(1) extra space), and in-place reversal (re-wire three pointers per step). Reach for a list when you insert and delete in the middle a lot and never index; reach for an array otherwise.

Pointers are the whole game

A node is two things: a value and a reference to the next node. The list is a chain of those, ending in null. Everything hard about linked lists is bookkeeping: which pointers you hold, the order you reassign them, and not dropping the only reference to the rest of the chain.

The classic bug is reassigning next before you have saved the node it pointed to, which orphans the tail. The fix is muscle memory: save the next node first, then re-wire.

prev, curr = None, head
while curr:
    nxt = curr.next   # save before we clobber it
    curr.next = prev  # re-wire
    prev, curr = curr, nxt
return prev            # new head

That six-line loop is in-place reversal, the single most-asked linked-list operation. O(n) time, O(1) space, no recursion needed.

The dummy-head trick

Operations at the head are special: there is no previous node to update. A dummy node before the real head removes that special case entirely. You point dummy.next at the head, do your splicing uniformly, and return dummy.next at the end.

dummy = ListNode(0, head)
prev = dummy
while prev.next:
    if prev.next.val == target:
        prev.next = prev.next.next  # delete works at head too
    else:
        prev = prev.next
return dummy.next

Without the dummy you write two branches: one for "the node to delete is the head," one for everything else. The dummy collapses them. Use it any time the head might change: deletion, merging two sorted lists, removing the Nth-from-end.

Fast and slow pointers

Move one pointer one step and another two steps per iteration. Two results fall out of this.

Cycle detection (Floyd's algorithm). If there is a loop, the fast pointer laps the slow one and they meet; if fast or fast.next hits null, the list is acyclic. This is O(1) space, unlike the obvious "store every visited node in a hash set" approach which costs O(n) memory.

Midpoint in one pass. When fast reaches the end, slow sits at the middle. You get the midpoint without first walking the list to count its length.

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow is the midpoint; fast/fast.next being None means no cycle

A worked check: list 1 -> 2 -> 3 -> 4 -> 5. After step one slow is at 2, fast at 3. After step two slow is at 3, fast at 5. fast.next is null, loop ends, slow points at 3, the middle. Five nodes, two iterations.

When a list beats an array, and when it does not

The honest take: arrays win most of the time. Contiguous memory and O(1) indexing beat a linked list's theoretical O(1) splice, because cache misses on pointer-chasing often cost more than shifting elements. Pick a list when you genuinely insert and delete in the middle frequently and never need random access: an LRU cache (doubly linked list plus hash map to splice an entry to the front in O(1)), a streaming ring buffer, or the free-list inside an allocator. If you find yourself writing node = node.next in a loop to reach an index, you wanted an array.

Why interviewers probe this

Linked lists are a clean test of pointer discipline with almost no algorithmic trick to memorize. The interviewer screens for whether you can mutate a structure in place without losing a reference, handle the head and empty-list edge cases, and reason about space. The strong-answer move is to reach for the dummy head unprompted and to use fast/slow for cycles instead of a hash set, then name the O(1) space win. The held-back follow-up is usually "now do it without recursion" (reversal) or "find where the cycle starts" (after meeting, reset one pointer to head and advance both at one step; they meet at the cycle entry).

Common misconceptions

• "Insertion is always O(1)." Only once you already hold the node before the insertion point. Finding that node is O(n). The O(1) is for the splice, not the search.
• "Linked lists save memory." Each node carries pointer overhead (8 bytes per pointer on 64-bit) plus allocator bookkeeping. For small values the overhead can exceed the data.
• "Cycle detection needs a visited set." Floyd's fast/slow does it in O(1) space. The hash set works but wastes O(n) memory and is the weaker answer.
• "Reversal needs recursion or a stack." The three-pointer iterative loop is O(1) space. Recursion is O(n) stack depth and can blow up on long lists.

Key takeaways

• Save next before re-wiring, or you orphan the rest of the list.
• The dummy head removes the head-is-special branch for insert, delete, and merge.
• Fast/slow pointers give cycle detection and midpoint in one pass with O(1) extra space.
• Default to arrays; choose a list only for frequent middle splicing with no indexing (LRU cache, ring buffer).