Linked list problems have a reputation. You see one in an interview and your brain immediately starts sweating about pointers, null references, and off-by-one catastrophes. You're mentally drawing arrows on a whiteboard, erasing them, drawing them again, losing track of which node points where, and wondering if you've accidentally created an infinite loop that will crash the interviewer's laptop. Here's the secret nobody tells you early enough: **linked list problems are one of the most pattern-based categories in all of LeetCode**. There are maybe 5 or 6 core patterns. Learn those, and you can solve virtually any linked list problem thrown at you. The pointers aren't the hard part — recognizing *which pattern to apply* is. That's what this guide is about. We're going to break down every major linked list pattern, solve real LeetCode problems with each one, and build the kind of intuition where you see a linked list problem and immediately think "oh, that's the fast/slow pointer thing" or "dummy node, easy." > Linked lists aren't pointer nightmares. They're pattern recognition exercises. Learn the patterns and the pointers take care of themselves. Let's get to it. --- ## Setup: The ListNode Before we solve anything, let's set up our building blocks. Every singly linked list problem on LeetCode uses a node structure like this: ```typescript class ListNode { val: number; next: ListNode | null; constructor(val: number = 0, next: ListNode | null = null) { this.val = val; this.next = next; } } ``` That's it. A value, and a pointer to the next node. The last node in the list points to `null`. ### Helper: Build a List from an Array Typing out `new ListNode(1, new ListNode(2, new ListNode(3)))` gets old fast. Let's make a helper: ```typescript function buildList(arr: number[]): ListNode | null { if (arr.length === 0) return null; const head = new ListNode(arr[0]); let current = head; for (let i = 1; i < arr.length; i++) { current.next = new ListNode(arr[i]); current = current.next; } return head; } // Usage: buildList([1, 2, 3, 4, 5]) // Creates: 1 → 2 → 3 → 4 → 5 → null ``` ### Helper: Print a List For debugging, being able to visualize the list is invaluable: ```typescript function printList(head: ListNode | null): string { const values: number[] = []; let current = head; while (current) { values.push(current.val); current = current.next; } return values.join(" → ") + " → null"; } // printList(buildList([1, 2, 3])) // "1 → 2 → 3 → null" ``` ### Helper: Convert List Back to Array Useful for testing: ```typescript function listToArray(head: ListNode | null): number[] { const result: number[] = []; let current = head; while (current) { result.push(current.val); current = current.next; } return result; } ``` Keep these handy. We'll use them throughout this guide. --- ## Pattern 1: The Dummy Node Trick This is the simplest pattern and possibly the most useful. If you take one thing from this entire article, let it be this: **when you're building or modifying a linked list, start with a dummy node**. ### Why? The biggest source of bugs in linked list code is handling the **head** of the list. What if the head needs to be removed? What if the new list starts with a different node? What if the list is empty? Every one of these cases requires special `if` checks — and every special check is a place where bugs hide. A **dummy node** (also called a sentinel node) is a fake node you put before the head. It's never part of the answer. Its only job is to give you a stable starting point so you never have to special-case the head. ``` Before: head → 1 → 2 → 3 → null After: dummy → 1 → 2 → 3 → null ↑ You return dummy.next as the real head ``` > The dummy node trick eliminates 90% of linked list edge case bugs. Use it aggressively. Let's see it in action. --- ### LeetCode 203: Remove Linked List Elements **Problem:** Remove all nodes from a linked list that have a specific value. ``` Input: 1 → 2 → 6 → 3 → 4 → 5 → 6 → null, val = 6 Output: 1 → 2 → 3 → 4 → 5 → null ``` #### Without a Dummy Node (Messy) ```typescript function removeElements(head: ListNode | null, val: number): ListNode | null { while (head && head.val === val) { head = head.next; } let current = head; while (current && current.next) { if (current.next.val === val) { current.next = current.next.next; } else { current = current.next; } } return head; } ``` See that first `while` loop? That's the special case for when the head itself needs to be removed. It's not terrible, but it's an extra thing to remember, an extra thing to get wrong. #### With a Dummy Node (Clean) ```typescript function removeElements(head: ListNode | null, val: number): ListNode | null { const dummy = new ListNode(0, head); let current = dummy; while (current.next) { if (current.next.val === val) { current.next = current.next.next; } else { current = current.next; } } return dummy.next; } ``` One loop. No special cases. The dummy node absorbs the edge case of removing the head. If every node gets removed, `dummy.next` is just `null`. Clean. **Step-by-step for `[1, 2, 6, 3, 4, 5, 6]`, val = 6:** ``` dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6 → null ↑ current current.next = 1 (val ≠ 6) → move forward dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6 → null ↑ current current.next = 2 (val ≠ 6) → move forward dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6 → null ↑ current current.next = 6 (val === 6) → skip it! current.next = current.next.next dummy → 1 → 2 → 3 → 4 → 5 → 6 → null ↑ current current.next = 3 (val ≠ 6) → move forward ...continue until all 6s are removed... Return dummy.next → 1 → 2 → 3 → 4 → 5 → null ✅ ``` **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ### LeetCode 86: Partition List **Problem:** Given a linked list and a value `x`, partition it such that all nodes less than `x` come before nodes greater than or equal to `x`. Preserve the original relative order. ``` Input: 1 → 4 → 3 → 2 → 5 → 2 → null, x = 3 Output: 1 → 2 → 2 → 4 → 3 → 5 → null ``` This is the dummy node trick on steroids. Instead of one dummy node, we use **two** — one for the "less than" list and one for the "greater than or equal to" list. Then we stitch them together. ```typescript function partition(head: ListNode | null, x: number): ListNode | null { const lessHead = new ListNode(0); const greaterHead = new ListNode(0); let less = lessHead; let greater = greaterHead; let current = head; while (current) { if (current.val < x) { less.next = current; less = less.next; } else { greater.next = current; greater = greater.next; } current = current.next; } greater.next = null; less.next = greaterHead.next; return lessHead.next; } ``` **The key insight:** We're splitting one list into two separate lists, then connecting them. Each list has its own dummy node, so we never worry about which node comes first. **Step-by-step for `[1, 4, 3, 2, 5, 2]`, x = 3:** ``` Scan 1: 1 < 3 → less list: [1] Scan 2: 4 ≥ 3 → greater list: [4] Scan 3: 3 ≥ 3 → greater list: [4, 3] Scan 4: 2 < 3 → less list: [1, 2] Scan 5: 5 ≥ 3 → greater list: [4, 3, 5] Scan 6: 2 < 3 → less list: [1, 2, 2] Connect: less list → greater list Result: 1 → 2 → 2 → 4 → 3 → 5 → null ✅ ``` Don't forget `greater.next = null` — without it, the last node in the greater list might still point back to a node in the less list, creating a cycle. This is one of those bugs that's incredibly hard to track down if you don't know to look for it. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ## Pattern 2: Fast and Slow Pointers (Tortoise and Hare) This is the pattern that makes people say "that's clever." Two pointers walk through the list at different speeds. The fast pointer moves 2 steps at a time, the slow pointer moves 1 step. This simple setup unlocks a shocking number of problems. **Why does it work?** Think of two runners on a track. If one runs twice as fast as the other: - When the fast runner finishes, the slow runner is at the halfway point - If they're on a circular track, the fast runner will eventually lap the slow one That's it. That's the entire intuition. Let's apply it. --- ### LeetCode 876: Middle of the Linked List **Problem:** Find the middle node of a linked list. If there are two middle nodes, return the second one. ``` Input: 1 → 2 → 3 → 4 → 5 → null Output: Node with value 3 Input: 1 → 2 → 3 → 4 → 5 → 6 → null Output: Node with value 4 (second middle) ``` The brute force approach: count all nodes, then walk to the middle. That's two passes. Can we do it in one? ```typescript function middleNode(head: ListNode | null): ListNode | null { let slow = head; let fast = head; while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; } return slow; } ``` **Visual walkthrough for `[1, 2, 3, 4, 5]`:** ``` Step 0: slow=1, fast=1 1 → 2 → 3 → 4 → 5 → null S F Step 1: slow=2, fast=3 1 → 2 → 3 → 4 → 5 → null S F Step 2: slow=3, fast=5 1 → 2 → 3 → 4 → 5 → null S F fast.next is null → stop. Slow is at 3 (the middle). ✅ ``` **For even-length `[1, 2, 3, 4, 5, 6]`:** ``` Step 0: slow=1, fast=1 Step 1: slow=2, fast=3 Step 2: slow=3, fast=5 Step 3: slow=4, fast=null (fast went past the end) Stop. Slow is at 4 (the second middle). ✅ ``` > When fast reaches the end, slow is at the middle. It's like having a friend who reads twice as fast — when they finish the book, you're on the middle page. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ### LeetCode 141: Linked List Cycle **Problem:** Determine if a linked list has a cycle (some node's `next` points back to an earlier node). This is the classic application of Floyd's Cycle Detection Algorithm. If there's a cycle, the fast pointer will eventually "lap" the slow pointer and they'll meet. If there's no cycle, the fast pointer will reach `null`. ```typescript function hasCycle(head: ListNode | null): boolean { let slow = head; let fast = head; while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; if (slow === fast) return true; } return false; } ``` **Why does this work mathematically?** Imagine the slow pointer is at some position in the cycle, and the fast pointer is behind it (also in the cycle). Each step, the fast pointer closes the gap by exactly 1 position (it moves 2 steps while slow moves 1, so the relative distance decreases by 1). Since the gap decreases by 1 every step, they *must* eventually meet. It's not a matter of luck — it's guaranteed. ``` Imagine a cycle of length 5: 1 → 2 → 3 ↑ ↓ 5 ← 4 Step 0: slow=1, fast=1 Step 1: slow=2, fast=3 Step 2: slow=3, fast=5 Step 3: slow=4, fast=2 Step 4: slow=5, fast=4 Step 5: slow=2, fast=2 → MATCH! Cycle detected. ✅ ``` > Floyd's algorithm works because the fast pointer closes the gap by 1 each step. In a cycle of length C, they'll meet within C steps after both enter the cycle. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ### LeetCode 142: Linked List Cycle II **Problem:** If a linked list has a cycle, return the node where the cycle *begins*. If there's no cycle, return `null`. This builds on the previous problem with a beautiful mathematical trick. ```typescript function detectCycle(head: ListNode | null): ListNode | null { let slow = head; let fast = head; while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; if (slow === fast) { let pointer = head; while (pointer !== slow) { pointer = pointer!.next; slow = slow!.next; } return pointer; } } return null; } ``` **Wait, why does moving one pointer back to the head and walking both at speed 1 find the cycle start?** Here's the math. Let's define: - **F** = distance from head to cycle start - **C** = cycle length - **K** = distance from cycle start to where slow and fast meet When they first meet: - Slow has traveled: **F + K** steps - Fast has traveled: **2(F + K)** steps (it moves twice as fast) - Fast has also gone around the cycle some number of times: **F + K + nC** (where n is the number of extra laps) So: **2(F + K) = F + K + nC** Simplify: **F + K = nC** Therefore: **F = nC - K** This means: the distance from the **head to the cycle start** (F) equals the distance from the **meeting point to the cycle start** going forward (nC - K). So if we put one pointer at the head and one at the meeting point, and walk both one step at a time, they'll meet at the cycle start. ``` Example: Head → [A] → [B] → [C] → [D] → [E] ↑ ↓ [H] ← [G] ← [F] F = 2 (head to C, the cycle start) C = 6 (cycle length: C→D→E→F→G→H→C) After detection, fast and slow meet at some point. Move one pointer to head, walk both at speed 1. They meet at C — the cycle start. ✅ ``` > The math behind Cycle II is elegant: the distance from the head to the cycle start equals the distance from the meeting point to the cycle start (modulo cycle length). Two pointers at speed 1 will converge there. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ### LeetCode 202: Happy Number **Problem:** A happy number is defined by: starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (it's happy) or it loops endlessly in a cycle (it's not). ``` Input: 19 1² + 9² = 82 8² + 2² = 68 6² + 8² = 100 1² + 0² + 0² = 1 → Happy! ✅ Input: 2 2² = 4 4² = 16 1² + 6² = 37 3² + 7² = 58 5² + 8² = 89 8² + 9² = 145 1² + 4² + 5² = 42 4² + 2² = 20 2² + 0² = 4 → We're back to 4! Cycle detected. Not happy. ❌ ``` **Wait — this isn't a linked list problem!** Or is it? Think about it: each number leads to exactly one next number. That's a linked list! And the question is: does the chain end at 1, or does it form a cycle? That's Floyd's algorithm in disguise. ```typescript function isHappy(n: number): boolean { function getNext(num: number): number { let sum = 0; while (num > 0) { const digit = num % 10; sum += digit * digit; num = Math.floor(num / 10); } return sum; } let slow = n; let fast = getNext(n); while (fast !== 1 && slow !== fast) { slow = getNext(slow); fast = getNext(getNext(fast)); } return fast === 1; } ``` Slow takes one step (one round of digit squaring). Fast takes two steps. If they meet and it's not at 1, there's a cycle — the number isn't happy. If fast hits 1, we're done. > Cycle detection isn't just for linked lists. Any sequence where each element determines the next can have a cycle. Floyd's algorithm works on all of them. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(log n) per step, O(1) total steps in practice (bounded) | | Space | O(1) | --- ### LeetCode 234: Palindrome Linked List **Problem:** Determine if a singly linked list is a palindrome. ``` Input: 1 → 2 → 2 → 1 → null Output: true Input: 1 → 2 → null Output: false ``` This is a combination problem. You need **three** techniques in one: 1. **Fast/slow pointers** to find the middle 2. **In-place reversal** to reverse the second half 3. **Comparison** to check if both halves match ```typescript function isPalindrome(head: ListNode | null): boolean { if (!head || !head.next) return true; let slow: ListNode | null = head; let fast: ListNode | null = head; while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; } let prev: ListNode | null = null; let current = slow; while (current) { const next = current.next; current.next = prev; prev = current; current = next; } let left: ListNode | null = head; let right: ListNode | null = prev; while (right) { if (left!.val !== right.val) return false; left = left!.next; right = right.next; } return true; } ``` **Step-by-step for `[1, 2, 3, 2, 1]`:** ``` Step 1: Find middle using fast/slow 1 → 2 → 3 → 2 → 1 → null S F (fast reached end) Middle is node 3. Step 2: Reverse from middle onward Second half before: 3 → 2 → 1 → null Second half after: 1 → 2 → 3 → null Step 3: Compare first half with reversed second half Left: 1 → 2 → 3... Right: 1 → 2 → 3... All match → palindrome! ✅ ``` > Palindrome linked list is a "combo" problem. Recognizing that it decomposes into find-middle + reverse + compare is the real skill. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ## Pattern 3: In-Place Reversal Reversing a linked list is one of the most fundamental operations. It comes up as a problem on its own, as a building block for other problems, and as an interview warm-up question. If you can reverse a linked list in your sleep, you're in great shape. The core idea: walk through the list, and at each node, flip its `next` pointer to point backward instead of forward. --- ### LeetCode 206: Reverse Linked List **Problem:** Reverse a singly linked list. ``` Input: 1 → 2 → 3 → 4 → 5 → null Output: 5 → 4 → 3 → 2 → 1 → null ``` #### The Iterative Approach We need three pointers: `prev`, `current`, and `next`. Think of it as a dance: 1. Save `current.next` (so we don't lose it) 2. Point `current.next` to `prev` (flip the arrow) 3. Move `prev` to `current` 4. Move `current` to the saved `next` ```typescript function reverseList(head: ListNode | null): ListNode | null { let prev: ListNode | null = null; let current = head; while (current) { const next = current.next; current.next = prev; prev = current; current = next; } return prev; } ``` **Let's trace through `[1, 2, 3, 4, 5]` step by step with ASCII art:** ``` Initial state: prev = null current = 1 null 1 → 2 → 3 → 4 → 5 → null Step 1: Save next=2, flip 1's pointer, advance null ← 1 2 → 3 → 4 → 5 → null P C Step 2: Save next=3, flip 2's pointer, advance null ← 1 ← 2 3 → 4 → 5 → null P C Step 3: Save next=4, flip 3's pointer, advance null ← 1 ← 2 ← 3 4 → 5 → null P C Step 4: Save next=5, flip 4's pointer, advance null ← 1 ← 2 ← 3 ← 4 5 → null P C Step 5: Save next=null, flip 5's pointer, advance null ← 1 ← 2 ← 3 ← 4 ← 5 null P C current is null → loop ends. Return prev (node 5). ✅ ``` > The reversal dance: save, flip, advance, advance. Four moves, every step. Burn this into your muscle memory. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ### LeetCode 92: Reverse Linked List II **Problem:** Reverse the nodes of a linked list from position `left` to position `right`. Do it in one pass. ``` Input: 1 → 2 → 3 → 4 → 5 → null, left = 2, right = 4 Output: 1 → 4 → 3 → 2 → 5 → null ``` This is the "surgical reversal" — you only reverse a portion of the list. The tricky part is reconnecting the reversed section to the parts before and after it. ```typescript function reverseBetween( head: ListNode | null, left: number, right: number ): ListNode | null { if (!head || left === right) return head; const dummy = new ListNode(0, head); let prev: ListNode = dummy; for (let i = 1; i < left; i++) { prev = prev.next!; } const tail = prev.next!; for (let i = 0; i < right - left; i++) { const next = tail.next!; tail.next = next.next; next.next = prev.next; prev.next = next; } return dummy.next; } ``` **Let's trace through `[1, 2, 3, 4, 5]`, left=2, right=4:** ``` Initial: dummy → 1 → 2 → 3 → 4 → 5 → null ↑ prev prev points to node 1 (the node before position 2). tail points to node 2 (the first node in the reversal range). Iteration 1 (move node 3 to front of reversed section): next = 3 tail.next = 4 (skip over 3) 3.next = 2 (3 points to prev.next which is 2) prev.next = 3 dummy → 1 → 3 → 2 → 4 → 5 → null ↑ ↑ prev.next tail Iteration 2 (move node 4 to front of reversed section): next = 4 tail.next = 5 (skip over 4) 4.next = 3 (4 points to prev.next which is 3) prev.next = 4 dummy → 1 → 4 → 3 → 2 → 5 → null ✅ ``` The technique here is "repeatedly take the next node after `tail` and move it to the front of the reversed section." It's elegant because `tail` doesn't actually move — it's always the original first node of the reversed range, which naturally ends up at the end of the reversed section. > For partial reversal, the dummy node is essential. It handles the case where `left = 1` (reversing from the head) without any special logic. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ### LeetCode 24: Swap Nodes in Pairs **Problem:** Given a linked list, swap every two adjacent nodes and return the new head. ``` Input: 1 → 2 → 3 → 4 → null Output: 2 → 1 → 4 → 3 → null ``` This is reversal on a smaller scale — we're reversing pairs of nodes. ```typescript function swapPairs(head: ListNode | null): ListNode | null { const dummy = new ListNode(0, head); let prev: ListNode = dummy; while (prev.next && prev.next.next) { const first = prev.next; const second = prev.next.next; first.next = second.next; second.next = first; prev.next = second; prev = first; } return dummy.next; } ``` **Step-by-step for `[1, 2, 3, 4]`:** ``` dummy → 1 → 2 → 3 → 4 → null P F S Swap pair (1, 2): 1.next = 3, 2.next = 1, prev.next = 2 dummy → 2 → 1 → 3 → 4 → null P F S Swap pair (3, 4): 3.next = null, 4.next = 3, prev.next = 4 dummy → 2 → 1 → 4 → 3 → null ✅ ``` **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ## Pattern 4: Merge / Combine Linked lists are natural for merging because you can stitch nodes together by just rewiring pointers — no shifting elements like you'd need to with arrays. These problems come up constantly. --- ### LeetCode 21: Merge Two Sorted Lists **Problem:** Merge two sorted linked lists into one sorted list. ``` Input: 1 → 2 → 4 → null 1 → 3 → 4 → null Output: 1 → 1 → 2 → 3 → 4 → 4 → null ``` This is the classic merge step from merge sort. And of course, we use a dummy node. ```typescript function mergeTwoLists( list1: ListNode | null, list2: ListNode | null ): ListNode | null { const dummy = new ListNode(0); let current = dummy; while (list1 && list2) { if (list1.val <= list2.val) { current.next = list1; list1 = list1.next; } else { current.next = list2; list2 = list2.next; } current = current.next; } current.next = list1 ?? list2; return dummy.next; } ``` **Walkthrough for `[1, 2, 4]` and `[1, 3, 4]`:** ``` Compare 1 vs 1: take from list1 → [1] Compare 2 vs 1: take from list2 → [1, 1] Compare 2 vs 3: take from list1 → [1, 1, 2] Compare 4 vs 3: take from list2 → [1, 1, 2, 3] Compare 4 vs 4: take from list1 → [1, 1, 2, 3, 4] list1 is empty, append remaining list2 → [1, 1, 2, 3, 4, 4] ✅ ``` Simple, predictable, and that `current.next = list1 ?? list2` at the end handles whichever list has remaining nodes — no special cases needed. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n + m) where n and m are the list lengths | | Space | O(1) | --- ### LeetCode 23: Merge K Sorted Lists **Problem:** Merge `k` sorted linked lists into one sorted list. ``` Input: [[1,4,5], [1,3,4], [2,6]] Output: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 → null ``` The brute force way: merge lists one at a time. That works, but it's O(kN) where N is the total number of nodes. We can do better with **divide and conquer** — merge lists in pairs, just like merge sort. ```typescript function mergeKLists(lists: (ListNode | null)[]): ListNode | null { if (lists.length === 0) return null; if (lists.length === 1) return lists[0]; const mid = Math.floor(lists.length / 2); const left = mergeKLists(lists.slice(0, mid)); const right = mergeKLists(lists.slice(mid)); return mergeTwoLists(left, right); } function mergeTwoLists( list1: ListNode | null, list2: ListNode | null ): ListNode | null { const dummy = new ListNode(0); let current = dummy; while (list1 && list2) { if (list1.val <= list2.val) { current.next = list1; list1 = list1.next; } else { current.next = list2; list2 = list2.next; } current = current.next; } current.next = list1 ?? list2; return dummy.next; } ``` **Why divide and conquer?** If you merge one list at a time (merge list 1 and 2, then merge the result with list 3, etc.), the merged result keeps growing. With divide and conquer, you're always merging lists of similar sizes: ``` Round 1: Merge pairs [L1, L2, L3, L4, L5, L6] → [merge(L1,L2), merge(L3,L4), merge(L5,L6)] Round 2: Merge pairs again → [merge(L12, L34), L56] Round 3: Final merge → [merge(L1234, L56)] ``` Each round processes all N nodes once, and there are log(k) rounds. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(N log k) where N = total nodes, k = number of lists | | Space | O(log k) for recursion stack | --- ### LeetCode 2: Add Two Numbers **Problem:** Two non-negative integers are represented as linked lists in reverse order. Each node contains a single digit. Add the two numbers and return the sum as a linked list. ``` Input: 2 → 4 → 3 (represents 342) 5 → 6 → 4 (represents 465) Output: 7 → 0 → 8 (represents 807) Because: 342 + 465 = 807 ``` The reverse order is actually a gift — it means the digits are already lined up for addition from least significant to most significant, exactly how you'd add by hand. ```typescript function addTwoNumbers( l1: ListNode | null, l2: ListNode | null ): ListNode | null { const dummy = new ListNode(0); let current = dummy; let carry = 0; while (l1 || l2 || carry) { const val1 = l1?.val ?? 0; const val2 = l2?.val ?? 0; const sum = val1 + val2 + carry; carry = Math.floor(sum / 10); current.next = new ListNode(sum % 10); current = current.next; l1 = l1?.next ?? null; l2 = l2?.next ?? null; } return dummy.next; } ``` **The beauty of this solution:** The `while (l1 || l2 || carry)` condition handles *everything*: - Different length lists? The `?? 0` treats missing digits as 0. - Final carry? The `|| carry` ensures we add one more digit if needed (like 99 + 1 = 100). **Step-by-step for `[2, 4, 3]` + `[5, 6, 4]`:** ``` Step 1: 2 + 5 + carry(0) = 7 → digit: 7, carry: 0 Step 2: 4 + 6 + carry(0) = 10 → digit: 0, carry: 1 Step 3: 3 + 4 + carry(1) = 8 → digit: 8, carry: 0 Result: 7 → 0 → 8 → null ✅ (represents 807) ``` > The carry logic in Add Two Numbers is the same as elementary school addition. Go digit by digit, carry the 1. The linked list just makes it natural. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(max(n, m)) | | Space | O(max(n, m)) for the result list | --- ## Pattern 5: Two Pointers with Gap We saw fast/slow pointers earlier where one moves at double speed. This pattern is different: both pointers move at the **same speed**, but one starts ahead. The gap between them is the key. --- ### LeetCode 19: Remove Nth Node From End of List **Problem:** Remove the nth node from the end of a linked list. ``` Input: 1 → 2 → 3 → 4 → 5 → null, n = 2 Output: 1 → 2 → 3 → 5 → null (removed the 4) ``` The naive approach: count the length, calculate the position from the start, then walk there. Two passes. Can we do it in one? **The n-gap trick:** Send a `fast` pointer n steps ahead. Then move both `fast` and `slow` together. When `fast` reaches the end, `slow` is right before the node we want to remove. ```typescript function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null { const dummy = new ListNode(0, head); let fast: ListNode | null = dummy; let slow: ListNode | null = dummy; for (let i = 0; i <= n; i++) { fast = fast!.next; } while (fast) { fast = fast.next; slow = slow!.next; } slow!.next = slow!.next!.next; return dummy.next; } ``` **Why `n + 1` steps ahead?** Because we want `slow` to land on the node *before* the one to remove, so we can rewire `slow.next`. **Trace for `[1, 2, 3, 4, 5]`, n=2:** ``` After advancing fast by n+1=3 steps: dummy → 1 → 2 → 3 → 4 → 5 → null S F Move both until fast is null: dummy → 1 → 2 → 3 → 4 → 5 → null S F dummy → 1 → 2 → 3 → 4 → 5 → null S F (null) slow is at node 3. Remove slow.next (node 4): slow.next = slow.next.next (node 5) Result: 1 → 2 → 3 → 5 → null ✅ ``` > The dummy node is critical here. If we need to remove the first node (n = length of list), the dummy node prevents us from needing special logic. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n) — one pass | | Space | O(1) | --- ### LeetCode 160: Intersection of Two Linked Lists **Problem:** Given two singly linked lists, find the node where they intersect. If they don't intersect, return `null`. ``` List A: 4 → 1 ↘ 8 → 4 → 5 → null List B: 5 → 6 → 1 ↗ Intersection at node 8. ``` There's a breathtakingly elegant solution. Walk pointer A through list A, then when it reaches the end, redirect it to the **head of list B**. Do the same for pointer B (redirect to head of A when it reaches the end). They'll meet at the intersection. **Why?** If list A has length `a` and list B has length `b`, and they share a tail of length `c`: - Pointer A travels: `a + (b - c)` = `a + b - c` - Pointer B travels: `b + (a - c)` = `a + b - c` They travel the same distance! So they arrive at the intersection at the same time. ```typescript function getIntersectionNode( headA: ListNode | null, headB: ListNode | null ): ListNode | null { let pointerA = headA; let pointerB = headB; while (pointerA !== pointerB) { pointerA = pointerA ? pointerA.next : headB; pointerB = pointerB ? pointerB.next : headA; } return pointerA; } ``` That's it. No length calculation, no extra space. Just two pointers taking the scenic route. **Walkthrough:** ``` List A: [4, 1, 8, 4, 5] (length 5) List B: [5, 6, 1, 8, 4, 5] (length 6) Shared tail: [8, 4, 5] (length 3) Pointer A: 4 → 1 → 8 → 4 → 5 → null → 5 → 6 → 1 → [8] ← meet here Pointer B: 5 → 6 → 1 → 8 → 4 → 5 → null → 4 → 1 → [8] ← meet here Both traveled 5 + 6 - 3 = 8 steps. ✅ ``` If there's no intersection, both pointers will reach `null` at the same time (after traversing both lists), so the loop ends and returns `null`. > This is one of the most beautiful algorithms in all of LeetCode. Two pointers traveling through each other's paths will always meet at the intersection — or at null if there isn't one. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n + m) | | Space | O(1) | --- ### LeetCode 143: Reorder List **Problem:** Reorder a list from `L0 → L1 → ... → Ln` to `L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...` ``` Input: 1 → 2 → 3 → 4 → 5 → null Output: 1 → 5 → 2 → 4 → 3 → null ``` This problem is a beautiful combo of three patterns we've already learned: 1. **Find the middle** (fast/slow pointers) 2. **Reverse the second half** (in-place reversal) 3. **Merge the two halves** (interleaving merge) ```typescript function reorderList(head: ListNode | null): void { if (!head || !head.next) return; let slow: ListNode | null = head; let fast: ListNode | null = head; while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; } let prev: ListNode | null = null; let current: ListNode | null = slow; while (current) { const next = current.next; current.next = prev; prev = current; current = next; } let first: ListNode | null = head; let second: ListNode | null = prev; while (second?.next) { const tmp1 = first!.next; const tmp2 = second.next; first!.next = second; second.next = tmp1; first = tmp1; second = tmp2; } } ``` **Step-by-step for `[1, 2, 3, 4, 5]`:** ``` Step 1: Find middle → slow at node 3 First half: 1 → 2 → 3 Second half: 3 → 4 → 5 Step 2: Reverse second half Reversed: 5 → 4 → 3 Step 3: Interleave Take from first (1), take from second (5): 1 → 5 Take from first (2), take from second (4): 1 → 5 → 2 → 4 Take from first (3), second has no more .next: 1 → 5 → 2 → 4 → 3 Result: 1 → 5 → 2 → 4 → 3 → null ✅ ``` > Reorder List is the ultimate "combine patterns" problem. If you can solve this one, you've internalized fast/slow, reversal, and merge. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ## Pattern 6: Rearrangement These problems ask you to reorganize nodes in specific ways. The key technique: split the list into groups, manipulate each group, then reconnect. --- ### LeetCode 328: Odd Even Linked List **Problem:** Group all odd-indexed nodes together, followed by all even-indexed nodes. The first node is considered odd, the second even, and so on. ``` Input: 1 → 2 → 3 → 4 → 5 → null Output: 1 → 3 → 5 → 2 → 4 → null ``` Similar to the partition problem — we split into two lists (odd-indexed and even-indexed) and stitch them together. ```typescript function oddEvenList(head: ListNode | null): ListNode | null { if (!head || !head.next) return head; let odd: ListNode = head; let even: ListNode = head.next; const evenHead: ListNode = even; while (even && even.next) { odd.next = even.next; odd = odd.next; even.next = odd.next; even = even.next; } odd.next = evenHead; return head; } ``` **Step-by-step for `[1, 2, 3, 4, 5]`:** ``` Initial: odd = 1, even = 2, evenHead = 2 1 → 2 → 3 → 4 → 5 → null Iteration 1: odd.next = 3 (skip even node 2) odd = 3 even.next = 4 (skip odd node 3) even = 4 Odd list: 1 → 3 Even list: 2 → 4 Iteration 2: odd.next = 5 (skip even node 4) odd = 5 even.next = null (5 has no next) even = null Odd list: 1 → 3 → 5 Even list: 2 → 4 Connect: odd.next = evenHead 1 → 3 → 5 → 2 → 4 → null ✅ ``` > We save `evenHead` at the start so we can reconnect after splitting. This is a pattern you'll see repeatedly — save the connection point before you start rewiring. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ### LeetCode 61: Rotate List **Problem:** Rotate the list to the right by `k` places. ``` Input: 1 → 2 → 3 → 4 → 5 → null, k = 2 Output: 4 → 5 → 1 → 2 → 3 → null ``` The insight: rotating a list by k is the same as making it circular, then cutting at the right spot. ```typescript function rotateRight(head: ListNode | null, k: number): ListNode | null { if (!head || !head.next || k === 0) return head; let length = 1; let tail: ListNode = head; while (tail.next) { tail = tail.next; length++; } k = k % length; if (k === 0) return head; tail.next = head; let stepsToNewTail = length - k; let newTail: ListNode = head; for (let i = 1; i < stepsToNewTail; i++) { newTail = newTail.next!; } const newHead = newTail.next; newTail.next = null; return newHead; } ``` **Step-by-step for `[1, 2, 3, 4, 5]`, k=2:** ``` Step 1: Find length = 5. Compute k % 5 = 2. Step 2: Make circular by connecting tail to head. 1 → 2 → 3 → 4 → 5 → (back to 1) Step 3: Find the new tail. Walk length - k = 3 steps from head. Start at 1, walk to node 3. New tail = 3, new head = 4. Step 4: Cut the circle. 3.next = null Result: 4 → 5 → 1 → 2 → 3 → null ✅ ``` The `k % length` handles cases where k is larger than the list length (rotating a 5-node list by 7 is the same as rotating by 2). **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ## The Master Problem: LRU Cache (LeetCode 146) This is the problem that ties everything together. It's not just a linked list problem — it's a **design** problem that happens to use a linked list as its backbone. It appears in interviews at every major tech company, and it tests whether you truly understand why linked lists exist. ### The Problem Design a data structure that follows the Least Recently Used (LRU) eviction policy: - `get(key)` — return the value if the key exists, otherwise return -1. Mark the key as recently used. - `put(key, value)` — insert or update. If the cache exceeds capacity, evict the least recently used key. **Both operations must be O(1).** ### Why a Linked List? Think about what we need: - **Quick lookup** by key → HashMap gives us O(1) lookup - **Track usage order** → We need to know which item was used least recently - **Move items to "most recent"** → Moving an element in an array is O(n). Moving a node in a doubly linked list is O(1). - **Remove the oldest item** → Removing from the end of a doubly linked list is O(1). A **doubly linked list** + **HashMap** gives us O(1) for everything. ### The Architecture ``` HashMap: key → Node (for O(1) lookup) Doubly Linked List (for O(1) reorder): head ↔ [most recent] ↔ [recent] ↔ ... ↔ [least recent] ↔ tail ↑ ↑ dummy head dummy tail ``` The most recently used item is always right after `head`. The least recently used is always right before `tail`. When we access an item, we move it to the front. When we need to evict, we remove from the back. ### Full TypeScript Implementation ```typescript class DLLNode { key: number; val: number; prev: DLLNode | null; next: DLLNode | null; constructor(key: number = 0, val: number = 0) { this.key = key; this.val = val; this.prev = null; this.next = null; } } class LRUCache { private capacity: number; private map: Map; private head: DLLNode; private tail: DLLNode; constructor(capacity: number) { this.capacity = capacity; this.map = new Map(); this.head = new DLLNode(); this.tail = new DLLNode(); this.head.next = this.tail; this.tail.prev = this.head; } private addToFront(node: DLLNode): void { node.prev = this.head; node.next = this.head.next; this.head.next!.prev = node; this.head.next = node; } private removeNode(node: DLLNode): void { node.prev!.next = node.next; node.next!.prev = node.prev; } private moveToFront(node: DLLNode): void { this.removeNode(node); this.addToFront(node); } private removeLRU(): DLLNode { const lru = this.tail.prev!; this.removeNode(lru); return lru; } get(key: number): number { if (!this.map.has(key)) return -1; const node = this.map.get(key)!; this.moveToFront(node); return node.val; } put(key: number, value: number): void { if (this.map.has(key)) { const node = this.map.get(key)!; node.val = value; this.moveToFront(node); return; } const newNode = new DLLNode(key, value); this.map.set(key, newNode); this.addToFront(newNode); if (this.map.size > this.capacity) { const lru = this.removeLRU(); this.map.delete(lru.key); } } } ``` ### How It Works Step by Step Let's trace through with capacity = 2: ``` cache = new LRUCache(2) cache.put(1, 1) Map: {1 → Node(1,1)} List: head ↔ [1:1] ↔ tail cache.put(2, 2) Map: {1 → Node(1,1), 2 → Node(2,2)} List: head ↔ [2:2] ↔ [1:1] ↔ tail cache.get(1) → returns 1, moves node to front List: head ↔ [1:1] ↔ [2:2] ↔ tail cache.put(3, 3) → capacity exceeded! Evict LRU (node 2) Map: {1 → Node(1,1), 3 → Node(3,3)} List: head ↔ [3:3] ↔ [1:1] ↔ tail cache.get(2) → returns -1 (evicted) cache.put(4, 4) → capacity exceeded! Evict LRU (node 1) Map: {3 → Node(3,3), 4 → Node(4,4)} List: head ↔ [4:4] ↔ [3:3] ↔ tail cache.get(1) → returns -1 (evicted) cache.get(3) → returns 3, moves to front cache.get(4) → returns 4, moves to front ``` ### Why Each Piece Matters - **`addToFront`**: O(1) — just rewire 4 pointers. - **`removeNode`**: O(1) — a doubly linked list lets you remove any node without traversal because you have the `prev` pointer. - **`moveToFront`**: O(1) — remove + add. - **`removeLRU`**: O(1) — the LRU is always `tail.prev`. - **HashMap lookup**: O(1) — maps the key directly to the node. The dummy `head` and `tail` nodes are our old friend — the sentinel/dummy node trick. They eliminate all the edge cases of "what if the list is empty" or "what if we're removing the only node." > The LRU Cache is the ultimate linked list problem because it demonstrates *why* linked lists exist: O(1) insertion and deletion when you have a reference to the node. Arrays can't do that. **Complexity:** | Metric | Complexity | |--------|-----------| | Time | O(1) for both `get` and `put` | | Space | O(capacity) | --- ## Pattern Recognition: When to Think Linked Lists Not every problem explicitly says "linked list." Here's how to recognize when these patterns apply: ### Signals That Scream "Dummy Node" - You're building a new list from scratch - The head of the result might change - You're filtering, splitting, or partitioning nodes - Edge cases around empty lists are tricky ### Signals That Scream "Fast/Slow Pointers" - "Find the middle" - "Detect a cycle" - Any sequence where each element leads to exactly one next element - The problem involves meeting points or convergence ### Signals That Scream "In-Place Reversal" - "Reverse the list" (obviously) - "Reverse a portion" or "reverse in groups" - "Check if palindrome" (reverse second half) - You need to process nodes from back to front but can't use extra space ### Signals That Scream "Merge" - "Combine sorted lists" - "Interleave two lists" - Digit-by-digit arithmetic (Add Two Numbers) - Any problem that processes two lists simultaneously ### Signals That Scream "Two Pointers with Gap" - "Nth from the end" - "Find where two lists meet" - You need a specific distance between two positions ### Signals That Scream "Rearrangement" - "Group nodes by some property" (odd/even, less/greater) - "Rotate" or "shift" - "Reorder" in a specific pattern > When you see a linked list problem, don't start coding. Spend 30 seconds identifying the pattern. The pattern tells you the approach, and the approach writes the code. --- ## Common Pitfalls These are the bugs that will eat your time in an interview if you're not watching for them. ### 1. Losing References ```typescript // BAD — you just lost the rest of the list current.next = someOtherNode; // The nodes that were after current are now gone forever // GOOD — save first, then rewire const saved = current.next; current.next = someOtherNode; someOtherNode.next = saved; ``` **Rule:** Before you change any `.next` pointer, ask yourself: "Am I about to lose a reference to nodes I still need?" If yes, save it first. ### 2. Not Handling Null ```typescript // This will crash if current is the last node const next = current.next.val; // 💥 current.next might be null // Safe version const next = current.next?.val; ``` **Rule:** Every time you write `.next`, think about whether that node could be `null`. ### 3. Forgetting to Break Cycles ```typescript // After connecting two lists, make sure the last node // of the combined list points to null greater.next = null; // Without this, you might create a cycle! less.next = greaterHead.next; ``` **Rule:** When you split and rejoin lists, explicitly set the final `.next` to `null`. ### 4. Off-by-One Errors in Position Counting Linked list positions can be 0-indexed or 1-indexed depending on the problem. Always clarify which one you're using and trace through with a small example. ### 5. Not Testing Edge Cases Always test your solution mentally with: - **Empty list**: `null` - **Single node**: `[1]` - **Two nodes**: `[1, 2]` - **All same values**: `[1, 1, 1, 1]` - **Operation at the head** - **Operation at the tail** > 80% of linked list bugs come from one thing: losing a reference. Save before you rewire. Always. --- ## Cheat Sheet ### Pattern → Problem Mapping | Pattern | Key Problems | When to Use | |---------|-------------|-------------| | **Dummy Node** | Remove Elements (203), Partition List (86), Merge Two Sorted Lists (21) | Building/modifying a list where the head might change | | **Fast/Slow** | Middle (876), Cycle (141), Cycle II (142), Palindrome (234) | Finding middle, detecting cycles, convergence problems | | **In-Place Reversal** | Reverse List (206), Reverse Between (92), Swap Pairs (24) | Reversing all or part of a list | | **Merge/Combine** | Merge Two (21), Merge K (23), Add Two Numbers (2) | Combining multiple lists or digit arithmetic | | **Two Pointers + Gap** | Remove Nth (19), Intersection (160), Reorder (143) | Finding nth-from-end, intersection, relative positioning | | **Rearrangement** | Odd Even (328), Rotate (61) | Grouping or reordering nodes by position/property | ### Templates **Dummy Node:** ```typescript const dummy = new ListNode(0, head); let current = dummy; // ... manipulate current.next ... return dummy.next; ``` **Fast/Slow (Find Middle):** ```typescript let slow = head, fast = head; while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; } // slow is at the middle ``` **Fast/Slow (Cycle Detection):** ```typescript let slow = head, fast = head; while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; if (slow === fast) return true; // cycle } return false; ``` **In-Place Reversal:** ```typescript let prev: ListNode | null = null; let current = head; while (current) { const next = current.next; current.next = prev; prev = current; current = next; } // prev is the new head ``` **Two Pointers with Gap:** ```typescript let fast = head, slow = head; for (let i = 0; i < n; i++) fast = fast!.next; while (fast) { fast = fast.next; slow = slow!.next; } // slow is n nodes behind fast ``` ### Big O Reference | Operation | Singly Linked List | Doubly Linked List | |-----------|-------------------|-------------------| | Access by index | O(n) | O(n) | | Search | O(n) | O(n) | | Insert at head | O(1) | O(1) | | Insert at tail (with tail pointer) | O(1) | O(1) | | Insert at position | O(n) | O(n) | | Delete at head | O(1) | O(1) | | Delete given node | O(n)* | O(1) | | Reverse | O(n) | O(n) | *O(n) for singly linked list because you need to find the previous node. With a doubly linked list, you already have `prev`, so it's O(1). --- ## Final Thoughts Linked list problems feel intimidating because they're *visual*. You have to hold pointer relationships in your head, track which node points where, and reason about what happens when you rewire things. That's genuinely hard — the first few times. But here's the thing: there are only so many patterns. We covered six in this guide, and they cover the vast majority of linked list problems you'll encounter: 1. **Dummy Node** — eliminate edge cases 2. **Fast/Slow Pointers** — find middles, detect cycles 3. **In-Place Reversal** — flip pointers backward 4. **Merge/Combine** — stitch lists together 5. **Two Pointers with Gap** — maintain relative positioning 6. **Rearrangement** — split and reconnect When you see a linked list problem, don't panic. Don't immediately start writing code. Take a breath, identify the pattern, and let the pattern guide your implementation. The pointers will take care of themselves. > The best linked list coders aren't the ones who can juggle the most pointers in their head. They're the ones who recognize patterns fast enough that they barely have to think about the pointers at all. Now go practice. Pick a pattern, solve 2-3 problems from that pattern, then move to the next. By the time you've gone through all six, linked lists won't be scary anymore. They'll be one of your strongest categories. Happy coding.

Problem Solving Patterns: Linked Lists, Made Simple