Week 6: Linked List

Pattern family: Linked List · Time budget: 13 hours · Prerequisites: Weeks 1 through 5 done, with the fast/slow two-pointer idea from Week 2 and the ListNode attribute access from the Week 0 refresher fresh. · Cold-revisit obligation: Min Stack, Search in Rotated Sorted Array.

Overview

A linked list is the first data structure in this course that you cannot index into. There is no arr[i]; there is only a chain of nodes, each holding a value and a single reference .next to the node after it, ending at None. Everything you do is pointer surgery: you walk the chain one .next at a time, and you rearrange it by reassigning those references. The whole skill this week is keeping track of pointers so that you never lose the rest of the list when you rewire a single .next.

There is very little to memorize. The pattern is three small primitives that you combine: find the middle with a fast and a slow pointer, reverse a chain in place by walking it and flipping each .next backward, and merge two chains by repeatedly attaching the smaller head. Almost every linked-list interview question is one of these three, or two of them stacked. The canonical problem this week, Reorder List, is all three at once, which is exactly why it is the canonical. Most of the work is training the move that fires before any code: name which of the three primitives the problem is asking for, and reach for a dummy head so the empty-list and first-node cases stop being special.

flowchart TD
    Q["Read the problem"] --> A{"Is the data a chain of nodes<br/>with .next and no index access?"}
    A -->|yes| B{"Which primitive does it need?"}
    A -->|no| G["Probably a different pattern.<br/>Keep reading the cues."]
    B -->|"the middle, or nth from end"| M["Fast/slow pointers:<br/>fast moves two, slow moves one."]
    B -->|"a cycle, do they meet"| C["Fast/slow pointers (Floyd's):<br/>if they meet, there is a cycle."]
    B -->|"flip the direction"| R["In-place reversal:<br/>walk it, point each .next backward."]
    B -->|"combine sorted chains"| K["Merge: attach the smaller head,<br/>advance that list, repeat."]

Notice: the decision happens before you code, and it has two beats. First, is this a pointer problem at all (a chain of nodes, no indexing)? Second, which of the three primitives (middle, reversal, merge) does it want? Naming the primitive out loud (principle 1) is what makes this diagram fire under pressure.

Warm-Up: Retrieve Before You Begin

Answer from memory, no peeking. This pulls forward the Week 0 refresher and the Week 2 two-pointer idea that this week leans on hardest.

From the refresher: given class ListNode with val and next, how do you read the value two nodes ahead of node, and what happens if the list is too short?
From the refresher: what does the multiple-assignment line a, b = b, a do, and why is it the right tool for moving two pointers at once without a temporary variable?
From Week 2: in a fast/slow pointer scheme, the fast pointer moves two steps for every one step the slow pointer moves. After the fast pointer reaches the end, where is the slow pointer?

Check your recall

1. You read it as `node.next.next.val`, chaining attribute access. If the list is too short, `node.next` is `None`, and then `node.next.next` raises `AttributeError: 'NoneType' object has no attribute 'next'`. That is why every step into a linked list is guarded by a `None` check (`if node and node.next: ...`) before you dereference. 2. `a, b = b, a` evaluates the entire right-hand side first (building the tuple `(b, a)`), then unpacks it into the names on the left, so the two names are rebound simultaneously. For pointer moves it lets you advance two pointers in one line, for example `prev, curr = curr, curr.next`, without a temporary and without one assignment clobbering the value the other still needs. 3. The slow pointer is at the middle of the list. The fast pointer covers twice the distance, so when it has walked the whole list, the slow pointer has walked half of it. (Whether "the middle" lands on the first or second of the two middle nodes for an even-length list depends on your exact loop condition, which is a detail you will pin down deliberately this week.)

Learning objectives

By the end of this week you can:

Recognize a linked-list problem from the cue (a chain of nodes, no index access, cycle detection, in-place reordering, “the middle” or “the nth from the end”) and reach for the right primitive without being told.
Apply the dummy-head idiom to remove the special cases for an empty list and the first node.
Construct the three core primitives from scratch: find the middle with fast/slow pointers, reverse a chain in place, and merge two sorted chains.
Trace a sequence of .next reassignments by hand and explain why no part of the list is lost at any step.
Analyze the time and space complexity of a pointer solution and name why most of these run in O(n) time and O(1) extra space.
Defend every line of each solution you commit, from memory, with no AI open, including the order of the pointer moves.

Recognition cue

“The data is a chain of nodes I can only reach through .next, with no index access” is the surface cue. Underneath it, the specific tells are: cycle detection (“does the list loop”), in-place reordering or reversal (“rearrange the nodes without building a new list”), and positional questions answered without counting (“the middle”, “the nth from the end”). When you see any of those, ask which of the three primitives (middle via fast/slow, in-place reversal, merge) the problem is built from. Most problems are one primitive; the harder ones are two or three stacked, and naming each piece is how you break them apart.

Core concepts to internalize this week

The dummy head (sentinel node). Create one throwaway node whose .next points at the real head, build your result by appending to it, and return dummy.next at the end. This removes the “is this the first node” special case and the “what if the list is empty” special case in one move. It is the single most useful idiom this week, and merging is where it earns its keep.
Fast and slow pointers (Floyd’s). Move one pointer two steps for every one step of the other. When the fast pointer runs off the end, the slow pointer sits at the middle. When the list has a cycle, the fast pointer laps the slow one and they collide, which is how you detect a loop in O(1) space. This is the same fast/slow idea you first met in Week 2, now on a chain instead of an array.
In-place reversal as a primitive. Walk the list with three pointers (prev, curr, and a saved next), and at each node point curr.next back at prev, then slide all three forward. The saved next is not optional: the moment you reassign curr.next, you have cut the link to the rest of the list, so you must grab the next node before you flip the pointer. This is the move that, done out of order, silently drops the tail of your list.
Merging as a primitive. To merge two sorted chains, keep a dummy head and a tail pointer; repeatedly attach whichever of the two current heads is smaller, advance that list, and advance tail. When one list runs out, attach the entire remaining other list in one step (its nodes are already sorted and already linked). No copying, no new nodes.
Why Merge K Sorted Lists scales two patterns together. Merging k lists naively (merge the first two, then merge the result with the third, and so on) is correct but slow. The faster approach keeps a min-heap of the current head of every list and repeatedly pops the global smallest, which is the heap pattern from Week 8 arriving early. The linked-list mechanics and the heap mechanics compose cleanly because the heap only ever holds k nodes at a time.
The doubly linked list paired with a hash map. Give each node both a prev and a next reference, and you can splice that node out of the chain and reinsert it at one end in O(1), with no walking, because you already hold both of its neighbors. Pair that ordering structure with a dict that maps each key to its node, and lookups are O(1) too: this is the LRU-cache design, and the same hash-map-plus-linked-list pairing is the building block for other structures that need O(1) updates by key as well as O(1) reordering.

Common misconception. “To reverse or reorder a list, I reassign node.next to the new target and move on.” Reality. The instant you write node.next = something_else, the link to everything that used to follow node is gone, and if you did not save it first, that part of the list is unreachable. Every safe reversal and reorder saves the next node into a temporary before reassigning the pointer: nxt = curr.next first, then curr.next = prev. Losing the rest of the list this way is the most common linked-list bug, and tracing your pointer moves on paper for a three-node list is how you catch it.

Common misconception. “Handling the empty list and the first node needs special if branches at the top of every function.” Reality. That is what the dummy head is for. By starting from a sentinel node whose .next is the real head and returning dummy.next at the end, the first real node is treated exactly like every other node, and an empty input falls out correctly with no extra branch (you return dummy.next, which is None). Reaching for the dummy head first is what keeps merge and similar functions short and correct.

Python idioms this week

You are not yet expected to be fluent, so here is the toolbox this week uses. If any is unfamiliar, open the Python refresher before Monday.

The ListNode class and attribute access: node.val, node.next, with None marking the end of the list. LeetCode hands you this class; you read and traverse it, you rarely define it.
A node class carrying both prev and next (a doubly linked node). Unlike the singly linked ListNode, you usually define this one yourself, and the extra back-reference is what makes the O(1) splice in the LRU-cache design possible.
None checks before every dereference: while node: and if node and node.next: so you never call .next on None.
Attribute reassignment to rewire links: node.next = other, the actual surgery of the pattern.
The dummy-node idiom: dummy = ListNode(); dummy.next = head; ... return dummy.next.
Multiple assignment for pointer moves: prev, curr = curr, curr.next and slow, fast = slow.next, fast.next.next, which advance two pointers in one line by evaluating the whole right side first.
heapq.heappush / heappop with tuple entries (node.val, i, node) for the k-way merge, where the integer i is a tiebreaker so two equal values never force Python to compare two ListNode objects (which are not comparable). This is previewed from Week 8.

These are tools you are allowed to know cold in an interview. The pattern (which primitive solves the problem, and the order of the pointer moves) is the part you build yourself.

Pattern Card requirement

Before you solve the canonical problem, write your Pattern Card at .tutor/pattern-cards/linked-list.md. It must contain:

The recognition cue, in your own words.
The algorithmic skeleton in pseudocode (sketch all three primitives: find the middle, reverse in place, merge two chains).
Time and space complexity, general form (and why most of these are O(n) time and O(1) extra space).
Three edge cases (the empty list, a single node, and a two-node list are good starts; a list with a cycle is a fourth worth noting).
One war story (a bug you actually hit this week); fill this in at the end of the week.

The first four sections must be present before you start the canonical deep-dive. The tutor will probe the card; it will not write any of it for you.

Canonical deep-dive

Problem: Reorder List (https://leetcode.com/problems/reorder-list/)

Reorder List is this course’s home for the three linked-list primitives, because it is all three stacked in one problem: find the middle, reverse the second half, then merge the two halves alternately. The full guided walk-through, with each primitive explained as a relation between pointers and the exact complexity, is in canonical/reorder-list.md. Work it there. You will implement it yourself, in your own work repo, and write a short debrief. The walk-through is deliberately not an answer key: it shows you how to think and stops short of code you could paste, so that the reversal and merge primitives are still yours to build in the practice set.

Practice set

Five problems, in this order. Each has its own folder under practice/ with the problem link, a complexity target for you to fill in, and the debrief template. Do not skip ahead. The first two are the reversal and merge primitives in isolation; the third is fast/slow pointers for cycle detection; the fourth stacks the merge primitive with the heap pattern; the fifth is a design problem that pairs a doubly linked list with a hash map for O(1) updates.

Reverse Linked List (practice/reverse-linked-list/). The in-place reversal primitive on its own. This is the single most reused move of the week; drill it until the three-pointer dance is automatic.
Merge Two Sorted Lists (practice/merge-two-sorted-lists/). The merge primitive on its own, and the cleanest possible use of the dummy head.
Linked List Cycle (practice/linked-list-cycle/). Fast/slow pointers (Floyd’s) to detect a loop in O(1) extra space.
Merge K Sorted Lists (practice/merge-k-sorted-lists/). The merge primitive scaled to k lists with a min-heap; this is where the linked-list and heap patterns compose.
LRU Cache (practice/lru-cache/). A design problem: build a fixed-capacity cache with O(1) get and put by pairing a doubly linked list with a hash map. This is the most-asked data-structure-design question, and it is where the doubly linked node (with prev and next) earns its place.

Each problem follows the five-beat rhythm.

The five-beat rhythm (every problem)

Pattern Card is written (you did this Monday).
Name the pattern aloud and write your approach as a plain-English comment before any code.
Struggle floor: 25 minutes unaided.
Hint ladder if needed: six rungs, one per ask.
Debrief: the five questions, in your commit message, before the next problem.

Reflect

Ten minutes in your notebook, in writing:

Explain it back: describe the three linked-list primitives to a peer who just finished Week 2, in three sentences (one per primitive).
Connect: the fast/slow pointer technique appears here for cycle detection and middle-finding, and you first met it in Week 2 on a sorted array. What is the same about the two uses, and what is different?
Monitor: which of the three primitives (middle, reversal, merge) still feels shakiest when you try to write it from memory? Write the one sentence about pointer order that would steady it.

Knowledge Check

Answer from memory first. Items marked ⟲ are spaced callbacks to earlier material.

What surface cue in a problem statement should make you reach for the linked-list primitives, and what are the three primitives?
In an in-place reversal, why must you save curr.next into a temporary before you reassign curr.next = prev?
What two special cases does a dummy head remove, and what do you return at the end when you use one?
⟲ From Week 2: a fast pointer moves two steps for every one step of a slow pointer. Name the two different questions this scheme answers on a linked list, and what signals the answer in each.
⟲ From Week 0: why do you add an integer tiebreaker to the heap entries (node.val, i, node) when merging k lists, instead of pushing (node.val, node)?

Answer key

1. The cue is a chain of nodes reachable only through `.next`, with no index access (plus the specific tells: cycle detection, in-place reordering or reversal, and positional questions like "the middle" or "the nth from the end"). The three primitives are: find the middle with fast/slow pointers, reverse a chain in place, and merge two sorted chains. 2. Because `curr.next = prev` overwrites the only reference to the rest of the list. If you have not saved the next node first, everything after `curr` becomes unreachable and you lose the tail. So you grab `nxt = curr.next`, then flip `curr.next = prev`, then advance with `prev, curr = curr, nxt`. 3. It removes the "this is the first node, so there is no previous node to update" special case and the "the list is empty" special case. You return `dummy.next`, which is the real head of the result (or `None` if the result is empty). 4. Middle-finding: when the fast pointer runs off the end of the list, the slow pointer is at the middle. Cycle detection: if the list loops, the fast pointer laps the slow one and they become the same node (`slow is fast`), which signals a cycle; if the fast pointer reaches `None` first, there is no cycle. 5. Because if two nodes have equal `val`, Python falls through to comparing the next tuple element, and two `ListNode` objects are not orderable (no `__lt__`), so the comparison raises `TypeError`. The integer `i` (a list index or an incrementing counter) is always comparable, so it breaks the tie before Python ever tries to compare the nodes.

Cold revisit

This Friday, before any new work, re-solve two prior problems cold: no notes, no prior code open, no AI, the standard 25-minute floor on each. The first solve taught the pattern; this blind re-solve is what makes it stick. Full instructions are in revisit.md.

Min Stack (Week 4, Stacks). A blind re-solve. Do not look at which pattern it is until you have named it yourself; recognizing it cold is the point.
Search in Rotated Sorted Array (Week 5, Binary Search). A blind re-solve, same rules.

Neither is a linked-list problem, and that is deliberate: the cold revisit trains recognition across the whole course, not just this week’s pattern. Noticing that neither one is a linked list (Min Stack is a stack carrying an auxiliary minimum, Search in Rotated Sorted Array is binary search deciding which half is sorted) is itself part of the exercise. Debrief each at the end and log the outcome in .tutor/revisit-log.md.

How to know you are done with this week

Pattern Card complete at .tutor/pattern-cards/linked-list.md, including the war-story field.
Canonical deep-dive done: Reorder List implemented yourself (all three primitives stacked) with your short debrief (in your work repo).
Five practice problems solved, each with a five-question debrief in its commit message.
.tutor/revisit-log.md updated by the tutor with this week’s problems and the two cold revisits, with dates.
.tutor/progress.md updated to “Week 6 complete; ready for Week 7.”

If any of the above is missing, the week is not done. The tutor will not advance you to Week 7 until all five are present.

Resources

Free, no account required:

[Article] Linked list, the data structure: https://en.wikipedia.org/wiki/Linked_list
[Article] Floyd’s cycle detection (the tortoise and the hare): https://en.wikipedia.org/wiki/Cycle_detection#Floyd’s_tortoise_and_hare
[Docs] Python classes (reading a node class): https://docs.python.org/3/tutorial/classes.html
[Docs] Python heapq (for the k-way merge): https://docs.python.org/3/library/heapq.html