Skip to content

Volume ITechnology

4.9.0 — Linked List: The Pattern ​

Recognition cue. The input is a linked list. That is the whole cue — these problems are not about choosing an algorithm, they are about pointer discipline. They are asked because manipulating pointers correctly is a clean test of careful thinking.

The four techniques ​

Almost every linked-list problem is one or two of these, combined.

python
# 1. DUMMY HEAD — removes every special case around the first node
dummy = ListNode(0, head)  # (1)
tail = dummy
...
return dummy.next  # (2)

# 2. REVERSE — save the way forward before you overwrite the pointer
prev, curr = None, head  # (3)
while curr:
    nxt = curr.next  # (4)
    curr.next = prev  # (5)
    prev, curr = curr, nxt  # (6)
return prev                 # (7) NOT curr — curr is None

# 3. SLOW AND FAST — middles, cycles, k-from-the-end
slow = fast = head  # (8)
while fast and fast.next:
    slow, fast = slow.next, fast.next.next  # (9)

# 4. HASH MAP OF NODES — when you need old-node-to-new-node, or node identity
old_to_new = {}  # (10)

The templates, line by line.

(1) Template 1 puts a fake node in front of the list, so the real first node has a node before it like every other node. (2) The answer starts after the fake node.

(3) Template 2 reverses a list. prev starts at nothing and curr at the head. (4) Save the way forward before changing anything. (5) Turn this node's arrow around. (6) Step both pointers forward. (7) When curr runs off the end, prev is the new head.

(8) Template 3 starts two pointers at the head. (9) One moves two steps for each step of the other, which finds middles and loops.

(10) Template 4 maps each original node to something else, usually its copy, keyed by the node object itself, as in 4.9.5.

The rules that prevent most bugs ​

Save before you overwrite. The moment you assign curr.next, the old value is gone. Every reversal saves nxt first.

Use a dummy head whenever nodes may be added or removed at the front. It converts "is this the head?" from a branch into nothing at all.

Return prev, not curr, after a reversal loop. The loop ends when curr is null.

Know which middle your slow-fast loop finds. while fast and fast.next gives the second middle on an even-length list; while fast.next and fast.next.next gives the first. Trace a four-node list rather than memorising it.

Cut the list before rewiring halves. If you reverse the second half without severing it from the first, you get a cycle.

Compare nodes by identity, is or ===, never by value.

The eleven problems ​

#ProblemThe one insight
4.9.1Reverse Linked List ★Save next before overwriting it
4.9.2Merge Two Sorted Lists ★The dummy head; attach the leftover whole
4.9.3Reorder List ★Middle, reverse, weave — three techniques in order
4.9.4Remove Nth Node From End ★Open a gap of n, then move both together
4.9.5Copy List with Random Pointer ★Create all nodes first, wire pointers second
4.9.6Add Two Numberswhile l1 or l2 or carry covers every case
4.9.7Linked List Cycle ★The gap shrinks by exactly one, so it cannot skip zero
4.9.8Find the Duplicate NumberAn array is a linked list if values are indices
4.9.9LRU Cache ★Hash map for lookup, doubly linked list for order
4.9.10Merge K Sorted Lists ★Pair up or use a heap — both O(N \log k)
4.9.11Reverse Nodes in K-GroupSeed prev with the node after the group

★ marks the Blind 75 subset.

What the interviewer will push on ​

"Why a dummy head?" So operations at the front need no special case. This is the most reusable answer in the chapter.

"Prove the slow and fast pointers must meet." The gap shrinks by exactly one per step and cannot go below zero, so it must hit zero.

"Why must an LRU cache use a doubly linked list?" Unlinking a node in O(1) requires its predecessor.

"Iterative or recursive?" Recursion is shorter for reversal and merging, and it costs O(n) stack. On a 100,000-node list that overflows, so iterative is the production answer.

"How do you handle the head being removed?" Dummy head. If they ask this, they are checking the same thing twice.

One thing to volunteer: draw the pointers before writing code. Every hard problem here is bookkeeping, and the failures come from people who start typing before they have the picture.

Recall

  • Four techniques cover the group: dummy head, reversal, slow and fast, and a map of nodes.
  • Reversal: save next first, and return prev, because curr is null when the loop ends.
  • The dummy head removes every special case for the first node — use it whenever nodes are added or removed at the front.
  • Slow and fast: know which middle your loop condition lands on, by tracing a four-node list.
  • Floyd's cycle detection works because the gap shrinks by exactly one, so it cannot skip past zero.
  • Cut the list before rewiring two halves, or you build a cycle.
  • LRU = hash map for lookup + doubly linked list for order, and the node stores its key so eviction can clean the map.
  • Merging k lists is O(N \log k) by pairing or by heap; one-at-a-time is O(Nk).

Next: 4.9.1 Reverse Linked List — the subroutine half this chapter is built from.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet