Chapter 3 · Intermediate · Prereq: Chapter 2

Linked Lists

Singly & Doubly Linked · Fast & Slow Pointers · Reversal · Merge · Cycle Detection — pointer manipulation patterns that appear in 30% of interview problems.

11 Sections 11 Practice Problems Intermediate ← Back to Roadmap

Section 1 — What Is a Linked List?

A linked list is a linear data structure where each element (node) stores a value and a pointer to the next node. Unlike arrays, nodes are not stored contiguously in memory — they can be scattered anywhere on the heap, connected only by pointers.

Real-World Analogy: A Treasure Hunt Each note (node) contains a clue (data) and the location of the next note (pointer). To reach clue #5, you must follow all 4 previous clues — there is no shortcut.

1.1 — Node Structure

// Singly linked list node
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
// Doubly linked list node (for LRU Cache, deque)
struct DListNode {
    int key, val;
    DListNode* prev;
    DListNode* next;
    DListNode(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
};

1.2 — Complexity vs Arrays

Access by index: O(n) — must traverse from head. (Arrays: O(1))
Search: O(n) — both structures
Insert/Delete at known position: O(1) — just rewire pointers. (Arrays: O(n) — must shift)
Insert/Delete at unknown position: O(n) — must find position first
Memory: Extra pointer per node. No wasted capacity like dynamic arrays.

Use Linked List when: frequent insert/delete at known positions, implementing stacks, queues, or adjacency lists. Not for random access.

Section 2 — Pattern: Fast & Slow Pointers (Floyd's Algorithm)

Two pointers move through the list at different speeds — fast moves 2 nodes per step, slow moves 1. They meet at meaningful positions.

Find Middle

When fast reaches end, slow is at middle. Use for palindrome check, merge sort on linked list.

Cycle Detection

If fast and slow meet, there's a cycle. If fast hits nullptr, no cycle.

Kth from End

Advance fast k steps first, then move both. When fast hits null, slow = kth from end.

Fast/Slow pointer templates

// Find middle — slow stops at middle
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
}
// slow = middle (left-middle for even length)

// Cycle detection (Floyd's)
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true; // cycle detected
}
return false;

// Kth node from end (two-pointer with gap k)
ListNode *fast = head, *slow = head;
for (int i = 0; i < k; i++) fast = fast->next; // advance fast by k
while (fast) { slow = slow->next; fast = fast->next; }
// slow = kth node from end

TimeO(n) SpaceO(1)

Section 3 — Pattern: Reversal

Reversing a linked list is O(n) time, O(1) space. Requires tracking three pointers: prev, curr, and next.

The 3-Pointer Dance Before breaking the link curr→next, save next first. Then redirect curr→prev. Advance: prev=curr, curr=next. Repeat until curr=nullptr. Return prev (new head).

// Reverse entire list — iterative (preferred)
ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr) {
        ListNode* nxt = curr->next;   // save next
        curr->next = prev;            // redirect
        prev = curr;                  // advance prev
        curr = nxt;                   // advance curr
    }
    return prev; // new head
}
// Reverse a sublist from position left to right
// (0-indexed) — use dummy node + find boundaries
ListNode dummy(0); dummy.next = head;
ListNode* pre = &dummy;
for (int i = 0; i < left-1; i++) pre = pre->next; // node before sublist
ListNode* curr = pre->next;
for (int i = 0; i < right-left; i++) {
    ListNode* nxt = curr->next;
    curr->next = nxt->next;
    nxt->next = pre->next;
    pre->next = nxt;
}
return dummy.next;

TimeO(n) SpaceO(1)

Section 4 — Pattern: Dummy Node

Adding a dummy node before the head eliminates edge-case handling for empty lists or removing the head node. Always return dummy.next as the real head.

Return dummy.next at the end, not head — the head may have been removed or changed.

// Remove nth node from end — dummy + two pointers
ListNode dummy(0); dummy.next = head;
ListNode *fast = &dummy, *slow = &dummy;
for (int i = 0; i <= n; i++) fast = fast->next; // gap of n+1
while (fast) { slow = slow->next; fast = fast->next; }
slow->next = slow->next->next; // remove target
return dummy.next;

// Delete node with specific value — dummy prevents head case
ListNode dummy(0); dummy.next = head;
ListNode* curr = &dummy;
while (curr->next) {
    if (curr->next->val == val) curr->next = curr->next->next;
    else curr = curr->next;
}
return dummy.next;

Section 5 — Pattern: Merge Two Sorted Lists

Compare heads of both lists. Take the smaller one, advance that pointer. Use a dummy node to avoid edge cases.

// Merge two sorted linked lists — O(m+n) time, O(1) space
ListNode dummy(0); ListNode* tail = &dummy;
while (l1 && 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 ? l1 : l2; // attach remaining
return dummy.next;

Section 6 — Hard Pattern: Reorder List

Combines multiple patterns: find middle (fast/slow), reverse second half, then merge two halves. L0→L1→…→Ln becomes L0→Ln→L1→Ln-1→L2→…

// Reorder List — O(n) time, O(1) space
void reorderList(ListNode* head) {
    // 1. Find middle
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next)
        { slow = slow->next; fast = fast->next->next; }
    // 2. Reverse second half
    ListNode *prev = nullptr, *curr = slow->next;
    slow->next = nullptr; // cut list at middle
    while (curr) { ListNode* nxt = curr->next; curr->next = prev; prev = curr; curr = nxt; }
    // 3. Interleave first half and reversed second half
    ListNode *first = head, *second = prev;
    while (second) {
        ListNode *fn = first->next, *sn = second->next;
        first->next = second; second->next = fn;
        first = fn; second = sn;
    }
}

Practice Problems

#	Problem	Pattern	Diff
1	876. Middle of the Linked List	Fast/Slow	Easy
2	83. Remove Duplicates from Sorted List	Traversal + pointer redirect	Easy
3	206. Reverse Linked List	Reversal (iterative)	Easy
4	92. Reverse Linked List II	Reversal (sublist)	Medium
5	141. Linked List Cycle	Fast/Slow cycle detection	Easy
6	21. Merge Two Sorted Lists	Merge + dummy node	Easy
7	19. Remove Nth Node From End of List	Dummy + two-pointer gap	Medium
8	2. Add Two Numbers	Simultaneous traversal + carry	Medium
9	143. Reorder List	Three-part: mid + reverse + merge	Medium
10	146. LRU Cache	Doubly linked list + HashMap	Medium
11	23. Merge K Sorted Lists	K-way merge (min-heap)	Hard