Linked Lists

Linked-list questions test whether pointer changes preserve the nodes you still need. Before editing a link, identify the processed part, the unprocessed part, and how they will reconnect.

1. Cost Depends on Which Node You Already Know

Head, tail and size must remain consistent after the empty-to-singleton and singleton-to-empty transitions. Compare node identity when detecting cycles or shared tails; equal values do not imply the same node. Clarify whether the solution may reuse input nodes or must allocate copies.

2. Use a Dummy Head and Preserve the Unread Suffix

A dummy node gives the real head a predecessor, so inserting, deleting or reconnecting at the front follows the same rule as elsewhere. Return dummy.next, not the dummy. In a merge, a tail pointer marks the end of the result and always attaches the smaller current node; when one input ends, attach the remaining suffix. Time is $O(n+m)$ and auxiliary space $O(1)$ when reusing nodes.

For reversal, prev is the already-reversed prefix and current is the first node of the untouched suffix:

def reverse_list(head):
    prev, current = None, head
    while current is not None:
        following = current.next
        current.next = prev
        prev, current = current, following
    return prev

Saving following before rewiring prevents losing the suffix. Each step transfers one node from the untouched part to the reversed part; prev is the new head at termination. Time is $O(n)$ and auxiliary space $O(1)$. A recursive reverse also costs $O(n)$ time but needs $O(n)$ stack space and must clear the old forward link to avoid a cycle.

For a sublist or block reversal, split the work: locate bounds, detach the section, reverse it, reconnect. Save the node before the section, its old head (the future tail), and the node after it. Reconnect before.next to the reversed head and the old head to after. Specify whether a final block shorter than k is reversed; Block Reversal defines its own contract.

3. Fast/Slow Pointers and Fixed Gaps

Middle: start both at the head and advance slow once, fast twice while fast and fast.next exist. For even length this selects the second middle. To end at the first middle before splitting, use a loop requiring fast.next and fast.next.next. Write down which half should receive the extra node.

Cycle: with speeds one and two, fast gains one position per iteration modulo the cycle length, so it must meet slow if a cycle exists. Stop when fast reaches null otherwise. After a meeting, reset one pointer to the head and move both one step at a time; their next meeting is the entry. The distance from head to entry matches the remaining distance from the meeting point modulo the cycle length. Time is $O(n)$, space $O(1)$.

Nth from the end: keep a lead pointer n nodes ahead of a follower. When the lead reaches the end, the follower identifies the desired position. For deletion, use a dummy and keep the follower at the predecessor; validate whether n can exceed the list length before advancing.

4. Compose Small Operations

Linked List Zip reorders 1 -> 2 -> 3 -> 4 -> 5 into 1 -> 5 -> 2 -> 4 -> 3: find the midpoint, cut the link between halves, reverse the second half, then alternate nodes from the two halves. Save both next pointers before each splice. Cutting first prevents the old midpoint link from forming a cycle during weaving.

The three phases are all linear, so their sum is $O(n)$, with $O(1)$ auxiliary space. The same decomposition supports palindrome checking: compare the first half with a reversed second half, then restore the second half if callers expect the input unchanged.

5. Key Takeaways

• Save current.next before changing it; otherwise the unprocessed suffix may become unreachable.
• Use a dummy when the head can change, and reconnect both ends of a reversed section.
• Define the even-length midpoint and short-final-block behavior explicitly.
• A tail pointer makes append constant-time, but does not make singly linked tail deletion constant-time.

Review Two Pointers for read/write and parallel scans, and Recursion for recursive contracts. Move to Trees when a node has multiple child links instead of one next link.