Linked List Techniques

Intuition

A linked list stores elements in separate nodes, each holding a value and a pointer to the next node (a singly linked list) or to both neighbors (a doubly linked list). If the last node points back to the first, the list is circular.

The trade-off against an array is the whole point:

Operation	Array	Linked list
Access the i-th element	O(1)	O(n), you must walk
Insert/delete at a known position	O(n), elements shift	O(1), rewire a few pointers
Memory layout	contiguous, cache friendly	scattered nodes plus pointer overhead

Inserting node x after node p is two pointer writes: x.next = p.next, then p.next = x. The order matters: overwrite p.next first and you lose the rest of the list. In a doubly linked list, removing p is p.prev.next = p.next and p.next.prev = p.prev.

Interview linked-list questions are almost never about the data structure itself; they test whether you can manipulate pointers without losing nodes. A small toolkit covers nearly all of them:

1. Dummy (sentinel) head. Start with a fake node before the real head so that "insert/delete at the head" is not a special case. Return dummy.next.
2. Two pointers. A fast/slow pair (2 steps vs 1 step) finds the middle and detects cycles; a pair with a fixed gap of n nodes finds the n-th node from the end in one pass.
3. In-place reversal with three pointers prev, cur, nxt.
4. Hash map + doubly linked list when you need O(1) lookup and O(1) reordering, as in an LRU cache.

When to use it in interviews / OAs

• The input is a ListNode chain and the follow-up asks for O(1) extra space: reverse (all, a sublist, in groups of k), reorder, partition, merge, sort (merge sort on lists), check palindrome (find the middle, reverse the second half, compare).
• "Detect a cycle" or "find where it starts", including disguised versions where the "list" is an implicit sequence x -> f(x): happy numbers, or finding the duplicate in an array whose values are indices.
• Design problems that need recency or ordering with constant-time moves: LRU cache, LFU cache (one list per frequency), browser history, text editor cursor, "all operations O(1)" key counters.
• You hold a reference to a node and must delete or move it in O(1).

Template

Basic building blocks: the node class, conversion helpers (handy when testing your own code), reversal, middle and Floyd's cycle detection.

from typing import Optional


class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None) -> None:
        self.val = val
        self.next = next


def from_list(values: list[int]) -> Optional[ListNode]:
    dummy = tail = ListNode()  # A dummy head removes the "empty list" special case.
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next


def to_list(head: Optional[ListNode]) -> list[int]:
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out


def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]:
    prev, cur = None, head
    while cur:
        nxt = cur.next  # Save the rest of the list before rewiring.
        cur.next = prev
        prev, cur = cur, nxt
    return prev


def middle_node(head: Optional[ListNode]) -> Optional[ListNode]:
    # slow moves 1 step, fast moves 2; for even length this returns the second middle.
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow


def cycle_start(head: Optional[ListNode]) -> Optional[ListNode]:
    # Floyd: the pointers meet inside the cycle; then one restarts from head,
    # and both move 1 step at a time until they meet at the cycle entry.
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            p = head
            while p is not slow:
                p, slow = p.next, slow.next
            return p
    return None


assert to_list(reverse_list(from_list([1, 2, 3]))) == [3, 2, 1]
assert middle_node(from_list([1, 2, 3, 4])).val == 3
h = from_list([1, 2, 3, 4, 5])
h.next.next.next.next.next = h.next  # 5 -> 2 makes a cycle.
assert cycle_start(h).val == 2 and cycle_start(from_list([1, 2])) is None

Why Floyd's second phase works: if the head is a steps from the cycle entry and the pointers meet b steps past the entry in a cycle of length c, the fast pointer has walked twice as far, which gives a + b = k * c for some integer k. So walking a more steps from the meeting point lands exactly on the entry, the same place a pointer starting from the head reaches after a steps.

Dummy-head patterns: merging two sorted lists and removing the n-th node from the end (using the same ListNode, from_list and to_list helpers as above).

def merge_sorted(a: Optional[ListNode], b: Optional[ListNode]) -> Optional[ListNode]:
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val:  # Taking from a on ties keeps the merge stable.
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b  # Append whatever remains.
    return dummy.next


def remove_nth_from_end(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)  # The head itself might be the node to remove.
    fast = slow = dummy
    for _ in range(n):  # Open a gap of n nodes between fast and slow.
        fast = fast.next
    while fast.next:
        fast, slow = fast.next, slow.next
    slow.next = slow.next.next  # slow stops right before the target.
    return dummy.next


assert to_list(merge_sorted(from_list([1, 4, 5]), from_list([2, 4]))) == [1, 2, 4, 4, 5]
assert to_list(remove_nth_from_end(from_list([1, 2, 3, 4]), 2)) == [1, 2, 4]
assert to_list(remove_nth_from_end(from_list([7]), 1)) == []

The LRU cache is the most famous linked-list design question. The hash map finds a node in O(1); the doubly linked list keeps nodes in recency order and lets you move or evict any node in O(1). Sentinel nodes at both ends remove every null check.

class _Node:
    __slots__ = ("key", "val", "prev", "next")

    def __init__(self, key: int = 0, val: int = 0) -> None:
        self.key, self.val = key, val
        self.prev = self.next = None


class LRUCache:
    def __init__(self, capacity: int) -> None:  # Assumes capacity >= 1.
        self.cap = capacity
        self.map: dict[int, _Node] = {}
        # Two sentinels: head.next is the most recent entry, tail.prev the least recent.
        self.head, self.tail = _Node(), _Node()
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node: _Node) -> None:
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node: _Node) -> None:
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            return -1
        self._unlink(node)  # Move to the front: now the most recently used.
        self._push_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node:
            node.val = value
            self._unlink(node)
        else:
            if len(self.map) == self.cap:
                lru = self.tail.prev  # Evict the least recently used entry.
                self._unlink(lru)
                del self.map[lru.key]  # This is why every node stores its key.
            node = _Node(key, value)
            self.map[key] = node
        self._push_front(node)


c = LRUCache(2)
c.put(1, 1)
c.put(2, 2)
assert c.get(1) == 1  # Key 1 becomes the most recent.
c.put(3, 3)  # Evicts key 2.
assert c.get(2) == -1 and c.get(3) == 3 and c.get(1) == 1

In Python, collections.OrderedDict already is a hash map with a linked list inside. Mention it, but expect the interviewer to ask for the manual version above.

from collections import OrderedDict


class LRUCacheOD:
    def __init__(self, capacity: int) -> None:
        self.cap = capacity
        self.d: OrderedDict[int, int] = OrderedDict()  # Order of keys = recency order.

    def get(self, key: int) -> int:
        if key not in self.d:
            return -1
        self.d.move_to_end(key)
        return self.d[key]

    def put(self, key: int, value: int) -> None:
        self.d[key] = value
        self.d.move_to_end(key)
        if len(self.d) > self.cap:
            self.d.popitem(last=False)  # Pop the oldest key.


c = LRUCacheOD(1)
c.put(1, 1)
c.put(2, 2)
assert c.get(1) == -1 and c.get(2) == 2

Complexity

• Traversal, search, finding the middle, reversal, cycle detection, merge: O(n) time, O(1) extra space (iterative versions).
• Insert/delete given a node (doubly linked) or given its predecessor (singly linked): O(1).
• LRU get and put: O(1) average time (hash map), O(capacity) space.
• Recursive list algorithms use O(n) stack space; in Python that fails beyond about 1000 nodes, so prefer iteration.

Common pitfalls

• Losing the rest of the list. Save cur.next before overwriting it; when inserting, link the new node to its successor before linking the predecessor to it.
• Null dereferences. Check fast and fast.next before fast.next.next. Decide what to return for an empty list up front.
• Head special cases. Removing or inserting at the head is where most bugs live; a dummy node makes the head an ordinary node.
• Off-by-one in "n-th from the end". With a dummy start and a gap of exactly n, slow stops before the target, which is what you need to unlink it.
• Comparing values instead of nodes. For cycles and intersections use identity (is), not == on values, since values may repeat.
• LRU details. Store the key inside the node so eviction can delete it from the map; update the value and move the node on put for an existing key; evict before inserting when the cache is full.
• Deleting a node given only that node. Copy the next node's value into it and unlink the next node. This trick fails for the tail, and it silently changes node identity, so mention both caveats.

Interview variations

• Reverse: whole list, between positions m and n, in groups of k (reverse each group with a dummy before it).
• Fast/slow: middle node, palindrome list, reorder list (middle, reverse second half, interleave), cycle detection and cycle entry, find the duplicate number.
• Gap pointers: remove n-th from the end, rotate a list by k (connect into a ring, then cut).
• Merge family: merge two sorted lists, merge k sorted lists (heap), sort a list (merge sort with the middle split).
• Intersection of two lists: walk both; when one pointer hits the end, jump to the other list's head. They meet at the intersection or both become None.
• Copy a list with random pointers: a hash map from old to new nodes, or interleave copies in place.
• Design: LRU cache, LFU cache, browser history, design a linked list with index operations.