Linked List Interview Patterns: Complete Guide

Linked list problems are among the most common in coding interviews. They test pointer manipulation, edge case handling, and your ability to think about data structures without random access. This guide covers every pattern you need, with templates you can apply immediately.

The 15 Patterns

Here is a quick overview of every pattern we will cover:

#	Pattern	When to Use
1	Dummy node	Head might change
2	Fast-slow pointers	Middle, cycle, nth from end
3	Reversal	Reorder, palindrome, k-group
4	Merge two lists	Sorted merge, interleave
5	Partition	Group by condition
6	Runner technique	Interleave halves
7	Sentinel deletion	Delete without predecessor
8	Recursive traversal	Reverse-order processing
9	Stack-based	Compare from end, palindrome
10	Hash map tracking	Cycle start, intersection, copy
11	In-place modification	Flatten, sort, reorder
12	Multiple passes	Length-dependent operations
13	Carry propagation	Add numbers represented as lists
14	Circular list	Josephus, rotation
15	Multi-level lists	Flatten nested structures

Pattern 1: Dummy Node

Use when: The head of the list might change (insertion at front, deletion of head, merging).

The dummy node (also called a sentinel) is a fake node placed before the head. It eliminates edge cases because you never need to check if the list is empty:

def delete_value(head, target):
    """
    Delete all nodes with the given value.
    The dummy node handles the case where head itself should be deleted.
    Time: O(n), Space: O(1)
    """
    dummy = ListNode(0, head)
    prev = dummy
    current = head

    while current:
        if current.val == target:
            prev.next = current.next  # Skip current
        else:
            prev = current
        current = current.next

    return dummy.next

Without a dummy node, you would need separate logic for deleting the head node versus other nodes. With a dummy, the logic is uniform.

Pattern 2: Fast-Slow Pointers

Use when: Finding the middle, detecting cycles, finding the nth node from the end.

def find_middle(head):
    """Return the middle node. For even length, returns the second middle."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


def find_nth_from_end(head, n):
    """Return the nth node from the end (1-indexed)."""
    fast = head
    for _ in range(n):
        fast = fast.next
    slow = head
    while fast:
        slow = slow.next
        fast = fast.next
    return slow


def has_cycle(head):
    """Detect if the list has a cycle."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

The fast pointer moves at 2x speed. When it reaches the end, slow is at the middle. The same idea detects cycles (they will meet) and finds the nth from end (maintain a gap of n).

Pattern 3: Reversal

Use when: Reordering, checking palindromes, reversing in groups.

def reverse_list(head):
    """Reverse entire list. Time: O(n), Space: O(1)."""
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev


def reverse_between(head, left, right):
    """
    Reverse nodes between positions left and right (1-indexed).
    LeetCode 92
    Time: O(n), Space: O(1)
    """
    dummy = ListNode(0, head)
    prev = dummy

    # Move to position before 'left'
    for _ in range(left - 1):
        prev = prev.next

    # Reverse 'right - left + 1' nodes
    current = prev.next
    for _ in range(right - left):
        next_node = current.next
        current.next = next_node.next
        next_node.next = prev.next
        prev.next = next_node

    return dummy.next

Key insight: Reversal between positions uses the “pull node to front” technique. Each iteration pulls the next node and inserts it right after prev.

Pattern 4: Merge Two Lists

Use when: Merging sorted lists, interleaving, or combining two processed halves.

def merge_sorted(l1, l2):
    """
    Merge two sorted lists into one sorted list.
    LeetCode 21
    Time: O(n + m), Space: O(1)
    """
    dummy = ListNode(0)
    tail = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 or l2
    return dummy.next

Pattern 5: Partition

Use when: Separating nodes into groups based on a condition.

def partition(head, x):
    """
    All nodes < x come before nodes >= x. Preserve relative order.
    LeetCode 86
    Time: O(n), Space: O(1)
    """
    less = ListNode(0)
    greater = ListNode(0)
    lt, gt = less, greater

    while head:
        if head.val < x:
            lt.next = head
            lt = head
        else:
            gt.next = head
            gt = head
        head = head.next

    lt.next = greater.next
    gt.next = None
    return less.next

Pattern 6: Runner Technique

Use when: You need to interleave the first half with the reversed second half (reorder list, palindrome check).

def is_palindrome(head):
    """
    Check if linked list is a palindrome.
    LeetCode 234
    Time: O(n), Space: O(1)
    """
    # Find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse second half
    prev = None
    while slow:
        next_node = slow.next
        slow.next = prev
        prev = slow
        slow = next_node

    # Compare
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

Pattern 7: Sentinel Deletion

Use when: You need to delete a node when you only have a reference to that node (not its predecessor).

def delete_node(node):
    """
    Delete a node when you only have access to that node (not head).
    Copy the next node's value and skip it.
    LeetCode 237
    Time: O(1), Space: O(1)
    """
    node.val = node.next.val
    node.next = node.next.next

Limitation: This cannot delete the tail node because there is no next node to copy from.

Pattern 8: Recursive Traversal

Use when: Processing nodes in reverse order without explicit reversal.

def print_reverse(head):
    """Print list values in reverse order using recursion."""
    if not head:
        return
    print_reverse(head.next)
    print(head.val)


def add_to_tail_recursive(head, val):
    """Add a node to the tail recursively."""
    if not head:
        return ListNode(val)
    head.next = add_to_tail_recursive(head.next, val)
    return head

Pattern 9: Stack-Based

Use when: You need to compare from the end, or process in reverse, without modifying the list.

def is_palindrome_stack(head):
    """Check palindrome using a stack. Time: O(n), Space: O(n)."""
    stack = []
    current = head
    while current:
        stack.append(current.val)
        current = current.next

    current = head
    while current:
        if current.val != stack.pop():
            return False
        current = current.next
    return True

Pattern 10: Hash Map Tracking

Use when: Detecting intersections, copying lists with random pointers, finding cycle starts.

def get_intersection_node(headA, headB):
    """
    Find the intersection node of two lists.
    LeetCode 160
    Time: O(n + m), Space: O(1)
    """
    a, b = headA, headB
    while a is not b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a


def copy_random_list(head):
    """
    Deep copy a list with random pointers.
    LeetCode 138
    Time: O(n), Space: O(n)
    """
    if not head:
        return None

    old_to_new = {}
    current = head
    while current:
        old_to_new[current] = ListNode(current.val)
        current = current.next

    current = head
    while current:
        clone = old_to_new[current]
        clone.next = old_to_new.get(current.next)
        clone.random = old_to_new.get(current.random)
        current = current.next

    return old_to_new[head]

Pattern 11: In-Place Modification

Use when: Reordering, flattening, or sorting without extra space.

def reorder_list(head):
    """
    Reorder: L0→Ln→L1→Ln-1→...
    LeetCode 143
    Time: O(n), Space: O(1)
    """
    if not head or not head.next:
        return

    # Find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse second half
    second = slow.next
    slow.next = None
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt

    # Merge alternating
    first, second = head, prev
    while second:
        f_next, s_next = first.next, second.next
        first.next = second
        second.next = f_next
        first = f_next
        second = s_next

Pattern 12: Multiple Passes

Use when: The operation depends on the list length (e.g., remove nth from end, split into k parts).

def remove_nth_from_end(head, n):
    """
    Remove the nth node from the end.
    LeetCode 19
    Time: O(n), Space: O(1)
    """
    dummy = ListNode(0, head)
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    target = length - n
    current = dummy
    for _ in range(target):
        current = current.next
    current.next = current.next.next

    return dummy.next

You can also solve this in one pass using the fast-slow pointer gap technique (Pattern 2).

Pattern 13: Carry Propagation

Use when: Adding numbers represented as linked lists.

def add_two_numbers(l1, l2):
    """
    Add two numbers represented as reversed linked lists.
    LeetCode 2
    Time: O(max(n, m)), Space: O(max(n, m))
    """
    dummy = ListNode(0)
    current = dummy
    carry = 0

    while l1 or l2 or carry:
        val = carry
        if l1:
            val += l1.val
            l1 = l1.next
        if l2:
            val += l2.val
            l2 = l2.next

        carry = val // 10
        current.next = ListNode(val % 10)
        current = current.next

    return dummy.next

Pattern 14: Circular List

Use when: Rotation problems, Josephus problem, round-robin scheduling.

def insert_into_sorted_circular(head, val):
    """
    Insert a value into a sorted circular linked list.
    LeetCode 708
    Time: O(n), Space: O(1)
    """
    new_node = ListNode(val)
    if not head:
        new_node.next = new_node
        return new_node

    prev, current = head, head.next
    while True:
        # Normal case: insert between prev and current
        if prev.val <= val <= current.val:
            break
        # At the boundary (max → min): val is new max or new min
        if prev.val > current.val and (val >= prev.val or val <= current.val):
            break
        prev = current
        current = current.next
        if prev is head:  # Full loop — all same values
            break

    prev.next = new_node
    new_node.next = current
    return head

Pattern 15: Multi-Level Lists

Use when: Flattening nested or multi-level linked lists.

def flatten(head):
    """
    Flatten a multilevel doubly linked list.
    LeetCode 430 (simplified for singly linked)
    Time: O(n), Space: O(depth) for recursion
    """
    if not head:
        return head

    current = head
    while current:
        if hasattr(current, 'child') and current.child:
            # Find tail of child list
            child_tail = current.child
            while child_tail.next:
                child_tail = child_tail.next

            # Insert child list after current
            child_tail.next = current.next
            current.next = current.child
            current.child = None

        current = current.next
    return head

Decision Flowchart

When you see a linked list problem, ask these questions in order:

1. “Does the head change?” If yes → use a dummy node.

2. “Do I need the middle, cycle, or nth from end?” If yes → use fast-slow pointers.

3. “Do I need to reverse (part of) the list?” If yes → use the reversal pattern. If between positions, use reverse-between.

4. “Am I combining two lists?” If sorted → merge sorted. If alternating → interleave merge.

5. “Am I grouping nodes by condition?” If yes → partition into separate lists, then join.

6. “Do I need to process from the end?” If O(1) space → reverse then process. If O(n) space → stack.

7. “Are there random/child pointers?” If yes → hash map for random, iterative flattening for child.

Common Interview Mistakes

Mistake 1: Not Handling Edge Cases

Always check these at the start:

# Empty list
if not head:
    return None

# Single node
if not head.next:
    return head

# Two nodes (many patterns need at least 3)
if not head.next.next:
    # Handle separately
    pass

Mistake 2: Creating Cycles

When rearranging nodes, the last node’s next might still point to a node earlier in the list. Always set the tail’s next to None:

# After any rearrangement:
tail.next = None  # ALWAYS do this

Mistake 3: Losing Nodes

Before changing current.next, save the next pointer:

# WRONG — loses everything after current
current.next = some_other_node

# RIGHT — save first
next_node = current.next
current.next = some_other_node
# ... use next_node later

Mistake 4: Wrong Loop Condition

# To process pairs, check BOTH:
while current and current.next:
    ...

# For fast-slow, check fast AND fast.next:
while fast and fast.next:
    ...

# NOT just 'while current' — you will dereference None

Mistake 5: Confusing Node Identity with Value Equality

# WRONG — compares values
if node1 == node2:

# RIGHT — compares object identity
if node1 is node2:

Time Complexity Cheatsheet

Operation	Time	Space
Traverse / search	O(n)	O(1)
Insert at head	O(1)	O(1)
Insert at tail (no tail pointer)	O(n)	O(1)
Insert at tail (with tail pointer)	O(1)	O(1)
Delete by value	O(n)	O(1)
Find middle	O(n)	O(1)
Detect cycle	O(n)	O(1)
Find cycle start	O(n)	O(1)
Reverse entire list	O(n)	O(1)
Reverse between positions	O(n)	O(1)
Merge two sorted lists	O(n + m)	O(1)
Sort (merge sort)	O(n log n)	O(log n)
Check palindrome	O(n)	O(1)
Copy with random pointers	O(n)	O(n)
Find intersection	O(n + m)	O(1)

Key insight: Most linked list operations are O(n) time and O(1) space. If your solution uses O(n) space, ask yourself if you can eliminate it with pointer manipulation.

Interview Strategy

1. Clarify constraints: Singly or doubly linked? Can I modify values or only pointers? Is the list sorted? Can it have cycles?

2. Start with brute force: Mention the O(n) space approach (array, hash map, stack) to show you understand the problem.

3. Optimize to O(1) space: Explain how pointer manipulation eliminates the need for extra storage.

4. Draw before you code: Sketch the pointer changes on paper. Show your interviewer the before/after states.

5. Handle edge cases explicitly: Write the empty list and single node checks first.

6. Test with small inputs: Walk through your code with a 3-node list.

Practice Problems by Pattern

Easy

1. LeetCode 206 — Reverse Linked List (Reversal)
2. LeetCode 21 — Merge Two Sorted Lists (Merge)
3. LeetCode 141 — Linked List Cycle (Fast-Slow)
4. LeetCode 876 — Middle of the Linked List (Fast-Slow)
5. LeetCode 237 — Delete Node in a Linked List (Sentinel)

Medium

6. LeetCode 2 — Add Two Numbers (Carry)
7. LeetCode 19 — Remove Nth Node From End (Multi-Pass / Fast-Slow)
8. LeetCode 24 — Swap Nodes in Pairs (Reversal)
9. LeetCode 61 — Rotate List (Circular)
10. LeetCode 86 — Partition List (Partition)
11. LeetCode 92 — Reverse Linked List II (Reversal)
12. LeetCode 138 — Copy List with Random Pointer (Hash Map)
13. LeetCode 142 — Linked List Cycle II (Fast-Slow)
14. LeetCode 143 — Reorder List (Runner)
15. LeetCode 148 — Sort List (Merge + Fast-Slow)
16. LeetCode 160 — Intersection of Two Linked Lists (Hash Map / Two Pointer)
17. LeetCode 234 — Palindrome Linked List (Runner)
18. LeetCode 328 — Odd Even Linked List (Partition)

Hard

19. LeetCode 23 — Merge k Sorted Lists (Merge + Heap)
20. LeetCode 25 — Reverse Nodes in k-Group (Reversal)

Key Takeaways

• There are exactly 15 patterns that cover virtually all linked list interview problems. Learn the template for each.
• The dummy node is the single most useful technique — it eliminates edge cases in deletion, insertion, and merging.
• Fast-slow pointers solve three different problem types (middle, cycle, nth from end) with the same core idea.
• Always save next before modifying pointers, and always set the final tail’s next to None.
• Most linked list problems can be solved in O(n) time and O(1) space. If you are using O(n) space, consider pointer manipulation instead.
• In interviews, start with the brute force, then optimize. Draw the pointer changes before coding.