06 — Linked List

Neetcode Week 5. Linked lists are the second-most-common interview topic after arrays. They feel awkward at first because you're juggling pointers — but every problem reduces to 5 patterns.

What a linked list is
Singly vs doubly linked
The dummy head pattern
Pattern A — Reversal
Pattern B — Fast & slow pointers
Pattern C — Merge two sorted lists
Pattern D — In-place rearrangement
Pattern E — Hashmap-augmented (LRU, Copy List)
Walked-through problems
Pitfalls
Practice list

1. What a linked list is

A linked list is a chain of nodes. Each node holds a value and a pointer to the next node.

┌────┬───┐    ┌────┬───┐    ┌────┬───┐    ┌────┬─────┐
│ 1  │ ●─┼───→│ 2  │ ●─┼───→│ 3  │ ●─┼───→│ 4  │ NULL│
└────┴───┘    └────┴───┘    └────┴───┘    └────┴─────┘
   head                                       tail

Versus an array which is a contiguous block:

Random access: array O(1), list O(n) (must walk).
Insert/delete at known position: array O(n) (shift), list O(1) (rewire pointers).
Memory: array packs tightly; list has per-node overhead (the next pointer + allocation header).
Cache: array is cache-friendly; list scatters in memory.

In interviews, you almost never use linked lists for storage. You use them because the problem hands you one and asks you to manipulate pointers.

Node definition

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

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

2. Singly vs doubly linked

Singly:    head → A → B → C → null
Doubly:    null ← A ⇄ B ⇄ C → null

Singly: only next. Doubly: next AND prev.

Doubly is needed for:

O(1) deletion when given only the node (you need prev to rewire).
LRU cache (move-to-front of a doubly-linked list in O(1)).
Browser back/forward.

Most LeetCode problems use singly unless stated otherwise.

3. The dummy head pattern

The single most useful trick for clean linked-list code.

When you might modify the head (or return a new head), allocate a dummy node that precedes the real head. Build off dummy.next. At the end, return dummy.next.

                            dummy
                              ↓
                            ┌───┐    ┌───┐    ┌───┐    ┌───┐
                            │ ? ├───→│ 1 ├───→│ 2 ├───→│ 3 ├─→ null
                            └───┘    └───┘    └───┘    └───┘
                                       ↑
                                    actual head (= dummy.next)

This eliminates every "is this the first node?" special case.

Example: remove all nodes equal to val

def remove_elements(head, val):
    dummy = ListNode(0, head)
    cur = dummy
    while cur.next:
        if cur.next.val == val:
            cur.next = cur.next.next      # skip
        else:
            cur = cur.next
    return dummy.next

Without dummy, you'd have a separate while head and head.val == val: head = head.next block. With dummy, all logic is uniform.

4. Pattern A — Reversal

Reverse a Linked List (Easy)

def reverse_list(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next      # 1. save next
        cur.next = prev     # 2. flip pointer
        prev = cur          # 3. advance prev
        cur = nxt           # 4. advance cur
    return prev             # new head

Visualize one iteration:

prev   cur          nxt
 ↓      ↓            ↓
null   1 → 2 → 3 → null

after step 1: nxt = cur.next = 2
after step 2: cur.next = prev → 1 → null
after step 3: prev = cur (=1)
after step 4: cur = nxt (=2)

now: null ← 1   2 → 3 → null
            ↑   ↑
           prev cur

Repeat until cur == null. Then prev is the new head.

Memorize the four lines. It's the foundational linked-list move and shows up inside many other problems.

Recursive version

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

Elegant but adds O(n) call-stack space. Iterative is preferred in interviews unless asked.

Reverse Sublist (Medium) — Reverse Nodes in K-Group (Hard)

The principle: locate the segment, detach, reverse, reattach. The dummy head + careful pointer juggling.

def reverse_k_group(head, k):
    dummy = ListNode(0, head)
    group_prev = dummy
    
    while True:
        # 1. Find kth node from group_prev
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if not kth: return dummy.next   # less than k remaining
        
        group_next = kth.next
        
        # 2. Reverse group
        prev, cur = group_next, group_prev.next
        while cur != group_next:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        
        # 3. Connect
        new_first = group_prev.next         # was group's first, now last
        group_prev.next = kth                # link previous part to new head
        group_prev = new_first              # advance for next group
    
    return dummy.next

Trace by drawing pictures the first 2 times. Then the pattern clicks.

5. Pattern B — Fast & slow pointers

Same direction; fast moves 2 steps, slow moves 1. Useful for:

Finding the middle (slow lands on middle when fast hits end).
Detecting cycles (fast catches slow if there's a cycle).
Finding cycle start.
Finding nth-from-end (slow stays n behind fast).

Find the Middle of a Linked List

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow                              # for even-length, slow is the second middle

Cycle Detection (Floyd's Tortoise and Hare)

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

Why does fast catch slow if there's a cycle? If both are inside a cycle of length C, the gap between them changes by ±1 each step (fast gains one). After at most C steps, they meet.

Finding Cycle Start (Linked List Cycle II)

After fast and slow meet, reset one to head and advance both at speed 1. They meet at the cycle start.

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Phase 2: find start
            ptr = head
            while ptr != slow:
                ptr = ptr.next
                slow = slow.next
            return ptr
    return None

Math: let L = distance head→cycle-start, C = cycle length, m = distance from cycle-start to meeting point. Slow moved L+m; fast moved 2(L+m); difference is multiple of C. So L + m ≡ 0 (mod C) → L = (k-1)C + (C - m). Walking L from head and L from meeting point both arrive at cycle-start.

(You don't need to recall the proof in interviews; just remember the algorithm.)

Find the Duplicate Number (Medium)

Array of n+1 integers in [1, n]. Exactly one value appears at least twice. Find it. O(n) time, O(1) space, no array modification.

Treat the array as a linked list where nums[i] is the "next pointer." Duplicate = cycle start.

def find_duplicate(nums):
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast: break
    
    ptr = nums[0]
    while ptr != slow:
        ptr = nums[ptr]
        slow = nums[slow]
    return ptr

A beautiful problem — the linked-list framing makes the O(1)-space solution possible.

Remove Nth Node from End (Medium)

Remove the n-th node counting from the end.

Two pointers. Advance fast n+1 steps. Then move both until fast hits null. Now slow.next is the target.

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    slow = fast = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next
    return dummy.next

Why n+1? So slow lands on the node before the one to remove.

6. Pattern C — Merge

Merge Two Sorted Lists (Easy)

def merge_two_lists(l1, l2):
    dummy = ListNode()
    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                     # whichever is non-null
    return dummy.next

Three points that come up in any merge problem:

Dummy head to avoid first-node special-case.
Tail pointer to grow the result in O(1).
Append remaining at the end with tail.next = l1 or l2.

Merge K Sorted Lists (Hard)

Two approaches:

A. Heap-based (cleanest): push the head of each list onto a heap; pop smallest, append, push its successor.

import heapq

def merge_k_lists(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))
    dummy = ListNode()
    tail = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

The i is a tie-breaker because nodes aren't comparable.

B. Divide and conquer: merge pairs, then pairs of pairs.

Both are O(N log k) where N = total nodes, k = number of lists.

7. Pattern D — In-place rearrangement

Reorder List (Medium)

1→2→3→4→5 becomes 1→5→2→4→3.

Strategy: find middle, reverse second half, weave.

def reorder_list(head):
    # 1. find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # 2. reverse second half (starting at slow.next)
    prev, cur = None, slow.next
    slow.next = None                         # cut!
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    
    # 3. weave first and reversed second
    first, second = head, prev
    while second:
        t1 = first.next
        t2 = second.next
        first.next = second
        second.next = t1
        first = t1
        second = t2

A combination of three patterns: middle (fast/slow), reverse, merge. Practice this until it flows.

Add Two Numbers (Medium)

(2→4→3) + (5→6→4) represents 342 + 465 = 807 → (7→0→8). Lists are little-endian.

def add_two_numbers(l1, l2):
    dummy = ListNode()
    tail = dummy
    carry = 0
    while l1 or l2 or carry:
        s = carry
        if l1: s += l1.val; l1 = l1.next
        if l2: s += l2.val; l2 = l2.next
        carry, digit = divmod(s, 10)
        tail.next = ListNode(digit)
        tail = tail.next
    return dummy.next

Note or carry in the loop condition — handles the case where the sum has more digits than either input (e.g., 999 + 1 = 1000).

8. Pattern E — Hashmap-augmented

Copy List with Random Pointer (Medium)

Each node has next and random (could point anywhere or null). Deep-copy.

Approach 1: hashmap. Map old node → new node. Two passes.

def copy_random_list(head):
    if not head: return None
    mapping = {}
    cur = head
    while cur:
        mapping[cur] = Node(cur.val)
        cur = cur.next
    cur = head
    while cur:
        mapping[cur].next = mapping.get(cur.next)
        mapping[cur].random = mapping.get(cur.random)
        cur = cur.next
    return mapping[head]

Approach 2: O(1) space by interleaving copies into the original list, then unweaving. Look this up after you've understood Approach 1; rare in interviews.

LRU Cache (Medium) — the classic system-design-y problem

O(1) get(key) and put(key, val). Evict least-recently-used when full.

Design: doubly linked list (for O(1) move-to-front, evict-tail) + hashmap (key → node, for O(1) lookup).

class Node:
    def __init__(self, key, val):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}                      # key → Node
        # dummy head and tail simplify edge cases
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _add_to_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
    
    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add_to_front(node)
            return node.val
        return -1
    
    def put(self, key, val):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, val)
        self.cache[key] = node
        self._add_to_front(node)
        if len(self.cache) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

Mental model:

Most-recently-used near head; least-recently-used near tail.
Every get/put brings the touched node to head.
Evict by removing tail.prev.

LRU is the template for O(1) cache problems. Memorize the structure.

9. Walked-through problems

Linked List Cycle (Easy)

Already covered above.

Reverse Nodes in K-Group (Hard)

Already covered above.

Palindrome Linked List (Easy/Medium)

Is the list a palindrome? O(n) time, O(1) space.

Strategy: find middle, reverse second half, compare.

def is_palindrome(head):
    # 1. find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # 2. reverse second half
    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev = slow
        slow = nxt
    
    # 3. compare
    left, right = head, prev
    while right:
        if left.val != right.val: return False
        left = left.next
        right = right.next
    return True

10. Pitfalls

Losing the head

head = head.next makes you lose the original head. Always save dummy.next if you need to return it, before any traversal.

Cycles forming accidentally

a.next = b; b.next = a; creates an infinite loop in any traversal. Be vigilant about loops you create.

Not handling empty list

if not head: return None (or whatever) at the top of most functions saves a NullPointerException.

Two-pointer null checks

while fast and fast.next is the right guard for the slow/fast pattern. Just while fast lets fast.next.next crash on the last step.

Forgetting to disconnect

When splitting (e.g., reorder list), you need to explicitly cut the original next pointer (slow.next = None) or you'll create a cycle.

Doubly-linked: forgetting `prev`

Both prev and next must be updated symmetrically during insert/delete, or the list becomes corrupt. Consider implementing helper methods like _link(a, b) that sets both directions.

Recursion depth

Long lists (10⁴+) crash recursive solutions in Python (default limit 1000). Either bump sys.setrecursionlimit or use iterative.

11. Practice list

#	Problem	Pattern	Difficulty
206	Reverse Linked List	Reversal	Easy
21	Merge Two Sorted Lists	Merge	Easy
143	Reorder List	Mid + reverse + merge	Medium
19	Remove Nth from End	Two-pointer gap	Medium
138	Copy List with Random Pointer	Hashmap	Medium
2	Add Two Numbers	Walk + carry	Medium
141	Linked List Cycle	Floyd	Easy
287	Find the Duplicate Number	Floyd as cycle	Medium
146	LRU Cache	DLL + hashmap	Medium
23	Merge K Sorted Lists	Heap	Hard
25	Reverse Nodes in K-Group	Sublist reverse	Hard
234	Palindrome Linked List	Mid + reverse	Easy

TL;DR ✅

Always use a dummy head when the head might change or you might return a new list.
Memorize the four-line reversal (prev / cur / nxt); it's the building block.
Fast & slow pointers find middle, detect cycles, find cycle start, and locate nth-from-end.
Floyd's reframe: "find duplicate in array" → cycle detection.
Merge K sorted lists = heap of heads, or divide-and-conquer pairs. Both O(N log k).
LRU = doubly linked list + hashmap. The canonical O(1) cache.
Cut explicitly when splitting to avoid stray cycles.

Next: 07-trees.md.

External resources

NeetCode Linked List playlist: https://www.youtube.com/playlist?list=PLot-Xpze53lc9PRDmIBzz_VyINcTxJ8aF
LRU Cache walkthrough: https://www.youtube.com/watch?v=7ABFKPK2hD4
VisuAlgo linked list: https://visualgo.net/en/list