Pattern 08 · Linked Lists

Linked List Operations

Pointer-based structures with no random access — every operation is a traversal, and mastery is nothing more than clean pointer manipulation. Three moves (dummy node, fast/slow, prev/curr/next) cover almost every interview question.

time O(n)space O(1)moves dummy · fast/slow · reversepractice 11 problems

01 core concept

A chain of pointers, nothing more

A linked list is a sequence of nodes where each node knows only its value and where the next node lives. There is no index arithmetic and no O(1) jumps — if you want the 5th node, you walk five steps.

Singly Linked List: head | v [1] --> [2] --> [3] --> [4] --> None Doubly Linked List: head tail | | v v [1] <--> [2] <--> [3] <--> [4]

list_node.pypython

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

How to recognize this pattern

The problem explicitly involves a linked list.
You need to reverse, merge, detect a cycle, or reorder nodes.
You need the middle node or the nth from the end.
The head node might change — insertion or deletion at the front.

02 key techniques

The four moves

Move 1Dummy node

Use when the head might change — deletion, insertion, merging. Without it, removing the head is a special case; with it, every node is handled uniformly and you return dummy.next at the end.

Before (without dummy -- messy edge case for head): if head needs to be removed: head = head.next # special case! After (with dummy -- uniform handling): dummy --> [1] --> [2] --> [3] --> None | Always return dummy.next as new head

dummy_node.pypython

dummy = ListNode(0)
dummy.next = head
# ... do work ...
return dummy.next

Move 2Two pointers (fast/slow)

slow moves one step per turn, fast moves two. When fast hits the end, slow is at the middle. The same idea with a fixed gap instead of a speed difference finds the nth node from the end in one pass.

Finding the middle (slow moves 1, fast moves 2): Step 0: [1] --> [2] --> [3] --> [4] --> [5] --> None S F Step 1: [1] --> [2] --> [3] --> [4] --> [5] --> None S F Step 2: [1] --> [2] --> [3] --> [4] --> [5] --> None S F Fast hits end --> slow is at middle (node 3)

Finding nth from end (advance fast by n first): Remove 2nd from end in [1, 2, 3, 4, 5]: Gap = 2: [1] --> [2] --> [3] --> [4] --> [5] --> None S F Move both until fast hits end: [1] --> [2] --> [3] --> [4] --> [5] --> None S F Slow is at node BEFORE the one to remove. slow.next = slow.next.next --> removes node 4

Move 3Iterative reversal (prev / curr / next)

The single most important linked-list skill. Walk the list once; at each node, save the next pointer, flip the current node's arrow backwards, then advance both prev and curr. Step through it below.

step 1 / 6walkthrough — reverse 1 → 2 → 3 → 4 in place

1curr

prev None

curr 1

reversed —

Setup: prev = None, curr = head. The list is still 1 → 2 → 3 → 4 → None. Nothing reversed yet.

or use arrow keys

reverse_list.py — LC 206, iterativepython

def reverse_list(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next   # Save next
        curr.next = prev        # Reverse pointer
        prev = curr             # Advance prev
        curr = next_node        # Advance curr

    return prev                 # New head

The sacred order

Save → flip → advance. If you flip curr.next before saving it, the rest of the list is gone forever. This four-line loop is worth memorizing verbatim.

Move 4Recursion

Natural for reversal, merging, and divide-and-conquer on lists. Recurse to the end, then rewire pointers as the stack unwinds:

reverse_list.py — recursivepython

def reverse_list(head):
    if not head or not head.next:
        return head

    new_head = reverse_list(head.next)  # Reverse the rest
    head.next.next = head               # Point next node back to us
    head.next = None                    # Remove old forward pointer

    return new_head

Recursive reversal unwinding: reverse([1] --> [2] --> [3]) reverse([2] --> [3]) reverse([3]) return [3] # base case [2].next.next = [2] # [3].next = [2] [2].next = None return [3] --> [2] [1].next.next = [1] # [2].next = [1] [1].next = None return [3] --> [2] --> [1]

03 strategy

Which move for which situation

Situation	Technique
Head might change	Dummy node
Find middle / detect cycle	Fast/slow pointers
Find nth from end	Two pointers with n gap
Reverse all or part of list	prev/curr/next iteration
Merge two sorted lists	Dummy node + compare loop
Complex reordering	Split + reverse + merge

04 core problems

The problems the moves compose into

LC 21Merge Two Sorted Lists

Dummy node + compare loop. Whoever has the smaller head donates a node; attach the survivor at the end.

merge_two_lists.pypython

def merge_two_lists(list1, list2):
    dummy = ListNode(0)
    curr = dummy

    while list1 and list2:
        if list1.val <= list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next
        curr = curr.next

    curr.next = list1 or list2    # Attach remaining
    return dummy.next

Merge [1,3,5] and [2,4,6]: dummy --> [1] --> [2] --> [3] --> [4] --> [5] --> [6] ^ ^ ^ ^ ^ ^ L1 L2 L1 L2 L1 L2 take take take take take attach

LC 19Remove Nth Node from End

Build a gap of n + 1 from the dummy so that when fast falls off the end, slow sits on the node before the one to delete.

remove_nth_from_end.pypython

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    slow = fast = dummy

    # Advance fast by n+1 steps
    for _ in range(n + 1):
        fast = fast.next

    # Move both until fast hits None
    while fast:
        slow = slow.next
        fast = fast.next

    # slow is right before the node to remove
    slow.next = slow.next.next
    return dummy.next

LC 141Detect Cycle — Floyd's Algorithm

Cycle detection with fast/slow: [1] --> [2] --> [3] --> [4] --> [5] ^ | | | +--- [7] <-- [6] Slow moves 1 step, fast moves 2 steps. If there's a cycle, fast WILL catch slow inside the cycle. No cycle: fast reaches None. Cycle: fast == slow at some point.

has_cycle.pypython

def has_cycle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False

LC 142Find the Cycle Start

After slow and fast meet inside the cycle: reset one pointer to the head, move both at speed 1, and they meet exactly at the cycle's entry point. The proof is three lines of algebra:

After slow and fast meet inside cycle: 1. Reset one pointer to head 2. Move both at speed 1 3. They meet at the cycle start Mathematical proof: Let a = distance from head to cycle start Let b = distance from cycle start to meeting point Let c = cycle length slow traveled: a + b fast traveled: a + b + c fast = 2 * slow --> a + b + c = 2(a + b) --> c = a + b --> a = c - b So moving a pointer from head and another from meeting point, both at speed 1, they meet at cycle start after 'a' steps.

detect_cycle.pypython

def detect_cycle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Found cycle, now find start
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow

    return None

LC 2Add Two Numbers

Dummy node + a running carry. The loop condition l1 or l2 or carry handles unequal lengths and a final carry in one stroke.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) represents 342 + 465 2 + 5 = 7, carry 0 4 + 6 = 10, carry 1, digit 0 3 + 4 + 1(carry) = 8 Output: 7 -> 0 -> 8 (represents 807)

add_two_numbers.pypython

def add_two_numbers(l1, l2):
    dummy = ListNode(0)
    curr = 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, digit = divmod(val, 10)
        curr.next = ListNode(digit)
        curr = curr.next

    return dummy.next

LC 143Reorder List — the three-step combo

Transform 1 → 2 → 3 → 4 → 5 into 1 → 5 → 2 → 4 → 3. This is the moves composed: find middle + reverse second half + merge alternating.

Reorder [1, 2, 3, 4, 5]: Step 1 - Split: [1, 2, 3] and [4, 5] Step 2 - Reverse: [1, 2, 3] and [5, 4] Step 3 - Merge: 1 -> 5 -> 2 -> 4 -> 3

reorder_list.pypython

def reorder_list(head):
    if not head or not head.next:
        return

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

    # Step 2: Reverse second half
    prev, curr = None, slow.next
    slow.next = None              # Cut the list
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # Step 3: Merge alternating
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

LC 234Palindrome Linked List

Same combo, different payoff: find the middle, reverse the back half, compare the halves front-to-front.

is_palindrome.pypython

def is_palindrome(head):
    # Find middle
    slow, fast = head, 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 both halves
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next

    return True

05 complexity

Complexity reference

Operation / Problem	Time	Space
Reverse linked list	O(n)	O(1)
Find middle	O(n)	O(1)
Detect cycle	O(n)	O(1)
Find cycle start	O(n)	O(1)
Merge two sorted lists	O(n + m)	O(1)
Remove nth from end	O(n)	O(1)
Add two numbers	O(max(m, n))	O(max(m, n))
Reorder list	O(n)	O(1)
Palindrome linked list	O(n)	O(1)
Merge k sorted lists (heap)	O(N log k)	O(k)

06 common mistakes

Where pointers go wrong

Mistake 1 — losing the next reference

During reversal, flipping curr.next before saving it orphans the rest of the list. Always next_node = curr.next first.

Mistake 2 — no dummy node

If the head might be removed or changed, skipping the dummy forces special-case code that is easy to get wrong under pressure.

Mistake 3 — forgetting None

Empty list, single node, two-node lists. Trace your loop by hand on each before declaring victory.

Mistake 4 — off-by-one on nth from end

To land on the node before the target, you need a gap of n + 1 (starting from the dummy), not n.

Mistake 5 — not cutting the list when splitting

In reorder-style problems, forget slow.next = None and the two halves stay connected — your merge loops forever.

Mistake 6 — modifying while reading

Palindrome checks that reverse in place mutate the input. Fine in interviews if you say so — but know that you did it, and optionally restore the list.

10 practice

Practice ladder

In this order — easiest first. Tick each one as you solve it, and re-solve anything that took more than 25 minutes two days later.

11 problems

easyLC 206

Reverse Linked List

prev/curr/next — the core technique. Do it iterative AND recursive.

easyLC 21

Merge Two Sorted Lists

Dummy node + compare-and-attach loop.

easyLC 141

Linked List Cycle

Floyd's fast/slow detection.

easyLC 234

Palindrome Linked List

Split + reverse + compare — combines the moves.

mediumLC 19

Remove Nth Node from End

Two pointers with an n-gap.

mediumLC 2

Add Two Numbers

Dummy node + carry digit math.

mediumLC 142

Linked List Cycle II

Floyd's + the a = c − b proof to find the cycle start.

mediumLC 143

Reorder List

Split + reverse + merge — the three-step combo.

mediumLC 148

Sort List

Merge sort on a list — divide and conquer.

hardLC 23

Merge k Sorted Lists

Min-heap of list heads, or pairwise divide & conquer.

hardLC 25

Reverse Nodes in k-Group

Chunked iterative reversal with careful reconnection.