Linked lists cheat sheet

How linked-list questions give you the chain

Each link is a small Link object with a value and a next reference; the last link's next is None. Pages take the head link. To test, build a chain from a Python list with a short helper and read it back with another, so test cases stay readable.

Turn a chain of links around

Walk the chain with three names: the link behind you, the current link and the one ahead. Save the link ahead, point the current link back, then step everyone forward. When you fall off the end, the link behind you is the new head. O(n) time, O(1) memory.

def turn_around(head: Link | None) -> Link | None:
    back: Link | None = None
    here = head
    while here is not None:
        ahead = here.next  # save it before the arrow moves
        here.next = back
        back, here = here, ahead
    return back

Does the chain loop back on itself?

Send a slow pointer one link per step and a fast pointer two. Without a loop the fast pointer reaches the end. With a loop, once both are inside it the fast one gains one link per step, so it lands on the slow one within one lap. O(n) time, O(1) memory.

def has_loop(head: Link | None) -> bool:
    slow = fast = head
    while True:
        if fast is None or fast.next is None:
            return False  # the quick pointer ran off the end
        fast = fast.next.next
        slow = slow.next if slow else None
        if slow is fast:
            return True

Drop the k-th link from the end

Put a placeholder link in front of the head. Move a lead pointer k links ahead, then move lead and trail together until lead is on the last link. Trail now sits just before the link to remove; skip it. The placeholder handles removing the head. One pass: O(n) time, O(1) memory.

def drop_from_end(head: Link | None, k: int) -> Link | None:
    front = Link(0, head)  # placeholder in case the head goes
    lead = trail = front
    for _ in range(k):
        lead = lead.next or lead
    while lead.next is not None:
        lead = lead.next
        trail = trail.next or trail
    trail.next = trail.next.next if trail.next else None
    return front.next

Weave two sorted chains into one

Start from a placeholder link and keep a tail pointer. At each step attach whichever head is smaller and advance that chain. When one chain runs out, attach the rest of the other in one move. O(n + m) time, O(1) extra memory.

def weave(a: Link | None, b: Link | None) -> Link | None:
    front = Link(0)
    tail = front
    while a is not None and b is not None:
        if b.val < a.val:
            a, b = b, a  # keep the smaller head in a
        tail.next = a
        tail, a = a, a.next
    tail.next = a if a is not None else b  # the rest is in order
    return front.next

Fold a chain: first, last, second, second-last

Three steps, each O(n): find the middle with slow and fast pointers, turn the second half around, then interleave the two halves one link at a time. Total O(n) time and O(1) memory.

Sum two numbers stored digit by digit

Walk both chains together, adding the digits and a carry. Each step writes (total % 10) and keeps total // 10 as the carry. Continue while either chain has links or the carry is non-zero. O(max(n, m)) time; the output chain, O(max(n, m)) links, is the only extra memory.

def add_digits(a: Link | None, b: Link | None) -> Link | None:
    front = Link(0)
    tail, carry = front, 0
    while a is not None or b is not None or carry:
        total = carry
        if a is not None:
            total, a = total + a.val, a.next
        if b is not None:
            total, b = total + b.val, b.next
        carry, digit = divmod(total, 10)
        tail.next = Link(digit)
        tail = tail.next
    return front.next

Does a chain read the same backwards?

Find the middle with slow and fast pointers, turn the second half around, then compare the halves link by link. O(n) time and O(1) memory. Turning the second half back afterwards restores the input, which is polite if the caller still needs it.

The placeholder head trick

It is an extra link placed in front of the real head. Every real link then has a predecessor, so removing or inserting at the head uses the same code as anywhere else. At the end you return placeholder.next. It costs one object and removes a whole class of edge-case bugs.

When a chain beats a Python list

A Python list is a dynamic array: O(1) indexing and appends, but O(n) inserts and removals near the front. A chain gives O(1) insert and remove at a link you already hold, but O(n) to find a position and poor memory locality. In practice, chains win when you hold references to links and splice often, such as in LRU caches, and deque covers most queue needs.