Linked List Techniques

Updated Nov 19, 2026 · 3 min read
On this page

    Linked list questions rarely need clever algorithms. They need careful pointer moves without losing the rest of the list. Four techniques cover nearly every interview question, and they combine: "reorder list" is find the middle, reverse the second half, then merge.

    Linked Lists covers the structure itself. Here we focus on the moves.

    When to recognise it

    • "Reverse" a whole list, a sublist, or groups of k: three-pointer reversal.
    • "Middle", "cycle", "where does the cycle start", "is it a palindrome": fast and slow pointers.
    • "k-th from the end", "remove the n-th from the end": two pointers with a gap of n.
    • Any change that might touch the head (delete, insert, merge, partition): a dummy node before the head.
    • "Do it in O(1) extra space": you cannot copy into an array, so you must rewire pointers.

    Technique 1: reverse in place

    Walk the list once. At each node: save next, point the node backwards, then step forward.

    Nodes 1, 2, 3, 4. Nodes 1 and 2 already point backwards to None; prev is on 2, cur on 3, nxt on 4. The link from 2 to 3 is cut. Below: the three assignments in order.
    Nodes 1, 2, 3, 4. Nodes 1 and 2 already point backwards to None; prev is on 2, cur on 3, nxt on 4. The link from 2 to 3 is cut. Below: the three assignments in order.
    class ListNode:
        def __init__(self, val=0, next=None):
            self.val, self.next = val, next
    
    
    def reverse(head):
        """Three pointers: save next, flip the link, step forward."""
        prev, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev, cur = cur, nxt
        return prev

    Time O(n), space O(1). The order inside the loop is the whole trick: save cur.next before overwriting it.

    Technique 2: fast and slow pointers

    slow moves one step, fast moves two. When fast runs off the end, slow is in the middle. If there is a cycle, fast laps slow and they meet.

    def middle(head):
        """Fast/slow: when fast reaches the end, slow is in the middle (second middle for even length)."""
        slow = fast = head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        return slow
    
    
    def has_cycle(head):
        slow = fast = head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            if slow is fast:
                return True
        return False

    To find where a cycle starts: after they meet, move one pointer back to the head and step both one node at a time; they meet again at the cycle's entrance.

    Technique 3: dummy node and a fixed gap

    A dummy node in front of the head means "remove the first node" is not a special case. A gap of n between two pointers puts the trailing one right before the n-th node from the end.

    List D, 1, 2, 3, 4, 5 where D is a dummy. lag points at 3 and lead at 5, n = 2 apart. Node 4, the second from the end, is red: lag.next = lag.next.next removes it.
    List D, 1, 2, 3, 4, 5 where D is a dummy. lag points at 3 and lead at 5, n = 2 apart. Node 4, the second from the end, is red: lag.next = lag.next.next removes it.
    def remove_nth_from_end(head, n):
        """Dummy node + gap of n: the dummy handles removing the head itself."""
        dummy = ListNode(0, head)
        lead = lag = dummy
        for _ in range(n):
            lead = lead.next
        while lead.next:
            lead, lag = lead.next, lag.next
        lag.next = lag.next.next
        return dummy.next

    Technique 4: merge with a tail pointer

    Building a new list is easiest with a dummy and a tail that always points at the last node:

    def merge_sorted(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

    Common bugs

    • Losing the rest of the list by overwriting cur.next before saving it.
    • while fast.next.next crashes when fast is None. Use while fast and fast.next.
    • Returning head after the head moved. Return dummy.next.
    • Comparing values to detect a cycle. Compare nodes (is), since values can repeat.
    • Off-by-one in the middle: for even lengths, the loop above returns the second middle. If you need the first one (for example, to cut the list in half), start fast at head.next.

    Say this in the interview

    • "I'll use a dummy node so removing the head isn't a special case, and return dummy.next."
    • "Fast moves two, slow moves one. If there's a cycle, the gap shrinks by one each step, so they must meet within one lap: O(n) time, O(1) space."
    • Draw three boxes and the arrows before you code, then say each assignment as you write it.

    Problems for this pattern

    1. Reverse Linked List: technique 1.
    2. Merge Two Sorted Lists: technique 4.
    3. Linked List Cycle: technique 2.
    4. Remove Nth Node From End of List: technique 3.
    5. Reorder List: middle, reverse, merge.
    6. Add Two Numbers: walk both lists with a carry and a dummy head.
    7. Copy List with Random Pointer: a map from old node to new node.
    8. LRU Cache: a doubly linked list plus a hash map.

    Related

    Linked Lists · Two Pointers · Heaps and Top-K (merging k lists) · Hash Maps