Linked Lists

What a linked list is

A chain of nodes, each holding a value and a pointer to the next node. Unlike arrays, nodes are scattered in memory.

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

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x = 0, ListNode* n = nullptr) : val(x), next(n) {}
};

In interviews, linked lists test careful pointer manipulation. The algorithms are short; the bugs come from losing a reference or dereferencing null.

Technique 1: The dummy (sentinel) head

When the head itself might change (deleting it, merging, inserting before it), create a fake node in front. Then every real node has a predecessor, and you return dummy.next.

def remove_elements(head, val):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        if prev.next.val == val:
            prev.next = prev.next.next     # unlink
        else:
            prev = prev.next
    return dummy.next

Technique 2: Reversal

The single most important list routine. Three pointers: prev, cur, nxt.

def reverse(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next     # 1. save the rest
        cur.next = prev    # 2. flip the arrow
        prev = cur         # 3. advance prev
        cur = nxt          # 4. advance cur
    return prev            # new head

ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *cur = head;
    while (cur) {
        ListNode* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
}

Recursive version (O(n) stack):

def reverse_rec(head):
    if not head or not head.next:
        return head
    new_head = reverse_rec(head.next)
    head.next.next = head      # the node after head now points back to head
    head.next = None
    return new_head

Reversing a sub-range (positions left..right)

def reverse_between(head, left, right):
    dummy = ListNode(0, head)
    before = dummy
    for _ in range(left - 1):
        before = before.next
    # repeatedly move the node after `start` to the front of the segment
    start = before.next
    for _ in range(right - left):
        moved = start.next
        start.next = moved.next
        moved.next = before.next
        before.next = moved
    return dummy.next

Technique 3: Fast & slow pointers

Two pointers moving at different speeds reveal structure in one pass with O(1) memory.

Find the middle

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

For the first middle (useful when splitting for merge sort), start fast = head.next.

Detect a cycle and find its entrance (Floyd)

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                  # they met inside the cycle
            p = head
            while p is not slow:          # move both 1 step at a time
                p, slow = p.next, slow.next
            return p                      # cycle entrance
    return None

ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) {
            ListNode* p = head;
            while (p != slow) { p = p->next; slow = slow->next; }
            return p;
        }
    }
    return nullptr;
}

This generalizes to any function x → f(x) on a finite set: Find the Duplicate Number, Happy Number.

Nth from the end

Move fast n steps ahead, then move both until fast hits the end.

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    slow = fast = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        slow, fast = slow.next, fast.next
    slow.next = slow.next.next
    return dummy.next

Technique 4: Merging

def merge(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
    ListNode dummy, *tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

Merge + middle-finding = merge sort for lists in O(n log n). Merge + heap = merge k lists in O(N log k).

Composite recipe: “split, reverse, combine”

A lot of medium problems are just three primitives chained together:

def reorder_list(head):
    # 1. middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next
    # 2. reverse second half
    second, slow.next = reverse(slow.next), None
    # 3. interleave
    first = head
    while second:
        n1, n2 = first.next, second.next
        first.next, second.next = second, n1
        first, second = n1, n2

Doubly linked lists

Each node has prev and next. With a hash map for O(1) node lookup this gives O(1) move-to-front and remove, the basis of LRU cache — see Design Problems.

class DNode:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

def remove(node):
    node.prev.next, node.next.prev = node.next, node.prev

def insert_after(anchor, node):
    node.prev, node.next = anchor, anchor.next
    anchor.next.prev = node
    anchor.next = node

Use sentinel head and tail nodes so you never deal with null neighbours.

Common mistakes

• Losing the rest of the list: always save cur.next before overwriting it.
• Null dereference: check fast and fast.next before fast.next.next.
• Forgetting to terminate: after splitting, set the first half's tail .next = None, or you create a cycle.
• Returning the wrong head: with a dummy node, return dummy.next, not head (the old head may have moved or been deleted).
• Comparing values instead of nodes when checking identity (is in Python).
• Using recursion on a 10⁵-node list in Python → recursion limit.

Complexity cheat sheet