Linked List Techniques

At a glance

The instinct

A linked list gives you no random access, so every clever trick comes from rewiring next pointers rather than moving data. Almost every interview question in this family is a remix of four routines: put a dummy node in front of the head, reverse a run of nodes, keep two pointers a fixed gap apart, and merge or splice two chains. If you can write those four from memory without a bug, harder problems become "which routines, in what order?"

Recognise it

Not this pattern if...

• You only need to detect a cycle or find a middle - that is the narrower fast & slow pointers pattern.
• You need O(1) access by index or binary search - copy to an array first, or reconsider the data structure.
• The problem is about an LRU cache - that is a hash map + doubly linked list design question.

Memory hack

Analogy: you are a climber on a rope ladder of carabiners. If you unclip one before clipping the next, you fall and the rest of the list is lost to the garbage collector. Every pointer change must happen after you have a handle on what it used to point to.

Say it out loud in the interview:

1. "I'll add a dummy node so the head is not a special case."
2. "Before I overwrite any .next, I'll save what it pointed to."
3. "I'll trace it on 0, 1, 2 and 3 nodes before I say I'm done."

How it works

Treat each problem as a pipeline of standard routines. Reorder List, for example, is three of them chained:

flowchart LR
    A[Find middle with slow and fast] --> B[Cut list after middle]
    B --> C[Reverse second half]
    C --> D[Merge halves alternately]

Reversal trace on 1 -> 2 -> 3 -> null:

When cur becomes null, prev is the new head.

For Remove Nth Node From End of List, start fast and slow at the dummy, move fast n + 1 steps, then move both until fast is null; slow.next is the node to unlink. Starting at the dummy is what lets you delete the real head.

Java template

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

class LinkedListKit {
    // Reverse the whole list; returns the new head.
    static ListNode reverse(ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next; // save
            cur.next = prev;          // flip
            prev = cur;               // step
            cur = next;
        }
        return prev;
    }

    // Reverse nodes at positions [left, right] (1-indexed) using a dummy.
    static ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode before = dummy;
        for (int i = 1; i < left; i++) before = before.next;
        ListNode tail = before.next;               // becomes the tail of the reversed part
        for (int i = 0; i < right - left; i++) {   // head-insertion: move tail.next to the front
            ListNode moved = tail.next;
            tail.next = moved.next;
            moved.next = before.next;
            before.next = moved;
        }
        return dummy.next;
    }

    // Remove the n-th node from the end with a fixed gap between two pointers.
    static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;
        for (int i = 0; i <= n; i++) fast = fast.next;
        while (fast != null) { fast = fast.next; slow = slow.next; }
        slow.next = slow.next.next;
        return dummy.next;
    }

    // Merge two sorted lists behind a dummy; reuse for many "build a new chain" problems.
    static ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0), tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = (a != null) ? a : b;
        return dummy.next;
    }
}

Complexity

Variations

• Sub-range reversal - reverse only positions left..right: Reverse Linked List II.
• Group reversal - check k nodes exist, reverse them, reconnect, repeat: Reverse Nodes in k-Group.
• Gap pointers - lead pointer k ahead: Remove Nth Node From End of List, Rotate List.
• Split and stitch - build two chains behind two dummies, then join: Partition List, Odd Even Linked List.
• Middle + reverse + compare/merge - Palindrome Linked List, Reorder List.
• Arithmetic on digits - carry through two lists: Add Two Numbers.
• Interleaved cloning - insert each copy after its original: Copy List with Random Pointer.
• Head switching - two pointers swap to the other list's head at the end: Intersection of Two Linked Lists.

Common mistakes

• Returning head instead of dummy.next after the head was removed or moved.
• Dereferencing fast.next.next without checking fast != null && fast.next != null.
• Forgetting to cut the list (set a .next to null) after splitting, which creates an accidental cycle.
• Off-by-one in gap pointers: the lead must move n + 1 steps from the dummy so slow stops before the target.
• In k-group reversal, reversing the final short group when the problem says to leave it unchanged.

All practice problems

15 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.