When to Use Linked List Techniques?

Core Idea: Sequential access with O(1) insertion/deletion at known positions. No random access, but pointer manipulation enables elegant in-place transformations.

Pattern Recognition:

Key Insight:

Pointer Manipulation: Unlike arrays, we can rewire connections without shifting elements. Master the three-pointer dance (prev, curr, next) and dummy node trick.

Why Not Array? When you need O(1) insert/delete at arbitrary positions (given a reference), or when problem naturally involves following chains of references.

Reverse Linked List

O(n) Time / O(1) Space

Goal: Reverse a singly linked list in-place.

Technique: Three-Pointer Reversal

Why Three Pointers? When we reverse curr's pointer, we lose access to the next node. Save it first! prev tracks the new "next" for curr, next saves the original chain.

Key Insight: At each step: save next, point curr back to prev, advance prev and curr. Return prev (new head) when curr becomes nil.

var prev *ListNode = nil curr := head for curr != nil: next := curr.Next // save next curr.Next = prev // reverse pointer prev = curr // advance prev curr = next // advance curr return prev // new head

Foundation Pattern:

Master this - it's used in reorder, k-group, palindrome problems.

Merge Two Sorted Lists

O(n+m) Time / O(1) Space

Goal: Merge two sorted lists into one sorted list.

Technique: Dummy Node + Two-Pointer Merge

Why Dummy Node? We don't know which list provides the head until we compare. Dummy lets us build the result without special-casing the first node.

Key Insight: Compare heads, attach smaller to result, advance that list. When one exhausts, attach the remainder of the other.

dummy := &ListNode{} curr := dummy for list1 != nil && list2 != nil: if list1.Val < list2.Val: curr.Next = list1 list1 = list1.Next else: curr.Next = list2 list2 = list2.Next curr = curr.Next // Attach remainder if list1 != nil: curr.Next = list1 else: curr.Next = list2 return dummy.Next

Don't Forget:

Handle nil inputs - return the other list directly.

Remove Nth Node From End

O(n) Time / O(1) Space

Goal: Remove the nth node from the end in one pass.

Technique: Two-Pointer Gap

Why Two Pointers? Create a gap of n nodes between right and left. When right hits nil, left is exactly at the node before the target.

Key Insight: Use dummy node so left can point to "before head" when removing the first node. Advance right by n first, then move both until right is nil.

dummy := &ListNode{Next: head} left, right := dummy, head // Create gap of n for n > 0: right = right.Next n-- // Move both until right hits nil for right != nil: left = left.Next right = right.Next // left is now before target left.Next = left.Next.Next return dummy.Next

Gap Pattern:

Offset pointers to find relative positions without counting length.

Reorder List

O(n) Time / O(1) Space

Goal: Reorder [0,1,2,3,4,5] to [0,5,1,4,2,3] - interleave front and back.

Technique: Find Middle + Reverse + Merge

Why This Combo? We need to access from both ends. Since we can't go backward, split at middle, reverse second half, then merge alternately.

Key Insight: Three-step process: (1) Fast/slow to find middle, (2) Reverse second half, (3) Interleave first and reversed second half.

// Step 1: Find middle (slow ends at middle) slow, fast := head, head.Next for fast != nil && fast.Next != nil: slow = slow.Next fast = fast.Next.Next // Step 2: Reverse second half second := slow.Next slow.Next = nil // cut the list var prev *ListNode for second != nil: tmp := second.Next second.Next = prev prev = second second = tmp // Step 3: Merge alternately first, second := head, prev for second != nil: tmp1, tmp2 := first.Next, second.Next first.Next = second second.Next = tmp1 first, second = tmp1, tmp2

Composite Pattern:

Combines fast/slow, reversal, and merge - know each piece!

Add Two Numbers

O(max(n,m)) Time / O(1) Space

Goal: Add two numbers represented as reversed linked lists (321 = 1->2->3).

Technique: Dummy Node + Carry Propagation

Why Reversed Order Helps: Least significant digit first matches natural addition order. No need to reverse - just iterate and carry.

Key Insight: Handle unequal lengths by treating missing nodes as 0. Continue while either list has nodes OR carry is non-zero.

dummy := &ListNode{} curr := dummy carry := 0 for l1 != nil || l2 != nil || carry != 0: v1, v2 := 0, 0 if l1 != nil: v1, l1 = l1.Val, l1.Next if l2 != nil: v2, l2 = l2.Val, l2.Next sum := v1 + v2 + carry carry = sum / 10 curr.Next = &ListNode{Val: sum % 10} curr = curr.Next return dummy.Next

Don't Forget:

Final carry! [9,9] + [1] = [0,0,1], not [0,0].

Copy List with Random Pointer

O(n) Time / O(n) Space

Goal: Deep copy a list where each node has a random pointer to any node.

Technique: HashMap Old-to-New Mapping

Why HashMap? When copying node A, its random might point to node B that we haven't created yet. Map lets us create nodes on-demand and link later.

Key Insight: For each node, ensure it and its next/random targets exist in map. Create if not exists, then wire up the copy's pointers.

mapping := map[*Node]*Node{nil: nil} p := head for p != nil: // Ensure current node exists if _, ok := mapping[p]; !ok: mapping[p] = &Node{Val: p.Val} // Ensure and link Next if p.Next != nil: if _, ok := mapping[p.Next]; !ok: mapping[p.Next] = &Node{Val: p.Next.Val} mapping[p].Next = mapping[p.Next] // Ensure and link Random if p.Random != nil: if _, ok := mapping[p.Random]; !ok: mapping[p.Random] = &Node{Val: p.Random.Val} mapping[p].Random = mapping[p.Random] p = p.Next return mapping[head]

O(1) Space Alternative:

Interleave copies (A->A'->B->B'), set randoms, then separate.

LRU Cache

O(1) All Operations

Goal: Implement cache with O(1) get/put, evicting least recently used on capacity overflow.

Technique: Doubly Linked List + HashMap

Why DLL + HashMap? HashMap gives O(1) key lookup. DLL gives O(1) removal and insertion at ends. Together: O(1) access with ordering.

Key Insight: DLL maintains usage order (head=LRU, tail=MRU). On access: remove node, add to tail. On eviction: remove from head. HashMap maps key to DLL node.

type LRUCache struct { head, tail *Node // dummy sentinels mapping map[int]*Node capacity int } func (c *LRUCache) Get(key int) int: if node, ok := c.mapping[key]; ok: c.remove(node) c.addToTail(node) return node.Val return -1 func (c *LRUCache) Put(key, val int): if node, ok := c.mapping[key]; ok: c.remove(node) node := &Node{Key: key, Val: val} c.addToTail(node) c.mapping[key] = node if len(c.mapping) > c.capacity: lru := c.head.Next c.remove(lru) delete(c.mapping, lru.Key)

Sentinel Nodes:

Dummy head/tail simplify edge cases - never remove them!

Why Key in Node?

When evicting LRU, we need its key to delete from HashMap.

Merge K Sorted Lists

O(n log k) Time / O(k) Space

Goal: Merge k sorted linked lists into one sorted list.

Technique: Min Heap

Why Min Heap? At each step, we need the smallest among k list heads. Heap gives O(log k) for this vs O(k) linear scan. Total: O(n log k).

Key Insight: Push all k heads to heap. Pop min, add to result, push its next (if exists). Repeat until heap empty.

heap := MinHeap{} // ordered by node.Val for each list in lists: if list != nil: heap.Push(list) dummy := &ListNode{} curr := dummy for heap.Len() > 0: node := heap.Pop() curr.Next = node curr = curr.Next if node.Next != nil: heap.Push(node.Next) return dummy.Next

Alternative: Divide & Conquer

Pair up lists, merge each pair, repeat. Like merge sort - O(n log k) time, O(1) extra space.

Trade-off:

Heap is simpler to code; D&C uses less space.

Reverse Nodes in K-Group

O(n) Time / O(1) Space

Goal: Reverse every k consecutive nodes. Leave remainder as-is if less than k.

Technique: Group-by-Group Reversal

Why Check First? Must verify k nodes exist before reversing. Otherwise, we'd reverse a partial group then struggle to undo.

Key Insight: For each group: (1) Count k nodes ahead, (2) If k exist, reverse them, (3) Connect reversed group to result. Track group boundaries carefully.

dummy := &ListNode{} curr := dummy p := head for p != nil: // Check if k nodes exist q := p for i := 0; i < k && q != nil; i++: q = q.Next if i < k: // less than k nodes left curr.Next = p break // Reverse k nodes prev := q // point to node after group groupHead := p for i := 0; i < k; i++: tmp := p.Next p.Next = prev prev = p p = tmp curr.Next = prev // connect to reversed group curr = groupHead // move to end of reversed group return dummy.Next

Key Detail:

Set prev = q (next group start) so reversed group connects properly.

Floyd's Cycle Detection (Tortoise and Hare)

O(n) Time / O(1) Space

Goal: Detect if a linked list has a cycle, and find where it starts.

The Lollipop Model

Visualize the list as a lollipop or letter "P": a straight stem leading to a loop.

Phase 1: Detect Cycle

slow, fast := head, head for fast != nil && fast.Next != nil: slow = slow.Next // 1 step fast = fast.Next.Next // 2 steps if slow == fast: // Cycle detected! They meet at Meeting Point break

Why They Meet: Fast gains 1 node per iteration. If cycle exists, fast will lap slow and eventually catch up inside the cycle.

The Math: Why x = z (mod L)

When they meet:

Equating Hare's distances:

2(x + y) = x + y + kL 2x + 2y = x + y + kL x + y = kL x = kL - y

The Key Insight:

x = kL - y x = (k-1)L + (L - y) x = (k-1)L + z // since L = y + z, so L - y = z

What This Means: Walking distance x from Head equals walking (k-1) full laps + z from Meeting Point. Both paths end at Cycle Start!

Phase 2: Find Cycle Start

// Reset one pointer to head p := head for p != slow: p = p.Next // walks x steps slow = slow.Next // walks z + (k-1)L steps return p // Both meet at Cycle Start

Visual Proof: Pointer from head walks x. Pointer from meeting point walks z (to cycle start) then possibly more full laps. They converge at cycle start.

Application:

Find Duplicate Number - treat array as linked list where arr[i] points to arr[arr[i]].

Cycle Detection

O(n) Time / O(1) Space

Goal: Return true if cycle exists in linked list.

Technique: Floyd's Tortoise and Hare

Why It Works: If there's a cycle, fast pointer enters it first. Slow follows. Fast gains 1 node per step, so it will eventually catch slow inside the cycle.

slow, fast := head, head for fast != nil && fast.Next != nil: slow = slow.Next fast = fast.Next.Next if slow == fast: return true return false

Check Both:

fast != nil AND fast.Next != nil (fast moves 2 steps).

Find Duplicate Number

O(n) Time / O(1) Space

Goal: In array of n+1 integers in range [1,n], find the duplicate without modifying array.

Technique: Floyd's on Array as Linked List

Why This Works: Treat index as "node" and arr[index] as "next pointer". Since values are in [1,n] and we have n+1 elements, there must be a cycle - the duplicate value is where multiple indices point.

Key Insight: The duplicate is the entrance to the cycle (multiple paths lead into it). Use Floyd's to find meeting point, then find cycle start.

// Phase 1: Find meeting point slow, fast := 0, 0 for: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break // Phase 2: Find cycle entrance (the duplicate) p := 0 for p != slow: p = nums[p] slow = nums[slow] return slow // The duplicate value

Array as Graph:

i -> nums[i] creates edges. Duplicate = node with in-degree > 1.

Linked List Patterns Summary

1. Dummy Node Pattern

Use When: Head might change (merging, removing first node, inserting at front).

Template: dummy := &ListNode{Next: head} ... return dummy.Next

Examples: Merge Two Lists, Remove Nth, Add Two Numbers.

2. Fast/Slow (Tortoise & Hare)

Use When: Finding middle, detecting cycles, nth from end.

Template: slow moves 1, fast moves 2. When fast ends, slow is at middle.

Examples: Reorder List (middle), Cycle Detection, Find Duplicate.

3. In-Place Reversal

Use When: Reversing all or part of list.

Template: Three pointers - prev, curr, next. Save next, reverse curr, advance all.

Examples: Reverse LL, Reorder List, Reverse K-Group.

4. Two-Pointer Gap

Use When: Finding nth from end in one pass.

Template: Advance right by n, then move both until right is nil.

Examples: Remove Nth From End.

5. HashMap + Linked Structure

Use When: Need O(1) lookup AND ordering/sequential access.

Template: HashMap for key->node, DLL for order. Update both on access.

Examples: LRU Cache, Copy Random List.

6. Merge Pattern

Use When: Combining sorted lists.

Template: Compare heads, attach smaller, advance. Handle remainders.

Examples: Merge Two Lists, Merge K Lists.

Common Thread:

Linked lists excel at O(1) insert/delete with known position. Use pointers creatively - multiple pointers at different speeds, gaps, or reversals unlock elegant O(1) space solutions.