Linked List
- Identify which of the five core operations a new linked list problem requires and in what order to apply them
- Apply three pointer safety rules (save before overwrite, preserve the remainder, verify exit state) that prevent the most common linked list bugs
- Use fast/slow pointers with the correct loop condition for each problem, understanding why the termination check determines which middle node you land on
- Solve composition problems (reorder list, palindrome check, merge sort) by combining the core operations rather than writing each from scratch
Linked list problems require managing pointer state without index-based access. The operations themselves are short, but the order of assignments matters: overwrite a pointer too early and the rest of the list becomes unreachable. The five operations in this guide cover the full problem space. Most hard problems are compositions of two or three of them.
Core Operations
A small set of operations covers the entire problem space. Every linked list question reduces to some combination of these.
| Block | When It Appears | What You Track |
|---|---|---|
| Traverse | Counting nodes, searching for a value, printing | curr |
| Reverse | Reorder, palindrome check, reverse between positions | prev, curr, next_node |
| Find middle (fast/slow) | Split for merge sort, palindrome, reorder | slow, fast |
| Detect cycle (Floyd) | Cycle detection, find cycle start | slow, fast |
| Merge sorted | Combine two sorted lists, merge sort merge step | dummy, tail |
Finding the Middle Node
Both pointers start at the head. The 2:1 speed ratio means when fast finishes the list, slow has covered exactly half the distance.
What Linked List Operations Actually Do
Arrays give O(1) random access. Linked lists do not. The only way to reach any node is to follow the chain from the start. There is no index arithmetic, no slice, no backward jump. Every operation must read forward in order.
This constraint means that every pointer write is permanent until reversed. Overwrite curr.next before saving what it pointed to, and every node after curr becomes unreachable. There is no way to recover them. No error appears. The code runs to completion with a silent truncation.
Each of the five operations has a fixed order of assignments that avoids this:
- In reversal, the forward reference is saved before the link is redirected.
- In splitting at the middle, the second half is saved before the first half's link is severed.
- In merging, the remainder is attached after the comparison loop exits.
- In Reverse Between, the predecessor and successor are both stored before the segment is reversed.
- In removal by gap, the gap is set to n+1 so the follower stops at the predecessor, not the target.
The operations are short because the rules are few. Violating the order loses nodes without producing any visible error.
The Dummy Head
Without a dummy, deleting or inserting at the head requires its own special case:
A dummy node sits before the real head. Every real node now has a predecessor, so the head is no longer a special case:
Pointer Safety
Three categories of pointer errors cause the majority of linked list bugs. Each one is easy to prevent once you know what to look for.
Rule 1: Save before overwrite
Before changing any .next pointer, save what it currently points to. Then change it. Then use the saved reference to keep moving forward.
Rule 2: Never lose the remainder
Before splitting, severing, or redirecting, make sure some variable still holds a reference to the rest of the list. When you split at the middle, save second = slow.next before setting slow.next = None. When merging, attach the leftover list after the loop: tail.next = l1 if l1 else l2.
Rule 3: Know your exit state
After a loop ends, know which variable holds what. After reversal: prev is the new head, curr is None. After fast/slow: slow is the middle, fast is at or past the end. Getting this wrong means returning the wrong node or breaking reconnections.
Pattern 1: Reverse List
The most common linked list operation. Three pointers coordinate each iteration: prev tracks the last reversed node, curr is the node being processed, and next_node saves the forward reference before it gets overwritten.
prev heads the reversed prefix and curr heads the unreversed suffix. This holds from the first iteration to the last. When curr becomes None, the entire list has been processed and prev is the new head.Linked List Reversal
Three pointers initialized. prev starts as null because the new tail points to nothing.
Step-by-Step Walkthrough
Trace of reversing [1 → 2 → 3 → 4 → 5] with pointer state at each step:
| Step | prev | curr | next_node | Action | List State |
|---|---|---|---|---|---|
| Init | None | 1 | - | Initialize pointers | 1→2→3→4→5 |
| 1 | None | 1 | 2 | Save, reverse, advance | None←1 2→3→4→5 |
| 2 | 1 | 2 | 3 | Save, reverse, advance | None←1←2 3→4→5 |
| 3 | 2 | 3 | 4 | Save, reverse, advance | None←1←2←3 4→5 |
| 4 | 3 | 4 | 5 | Save, reverse, advance | None←1←2←3←4 5 |
| 5 | 4 | 5 | None | Save, reverse, advance | None←1←2←3←4←5 |
| End | 5 | None | - | curr is None, loop exits | Return prev (5) |
curr.next = prev, the original next node is gone. If you then do curr = curr.next, curr moves to prev (backward), not forward. The list after curr becomes permanently unreachable.curr = curr.next instead of curr = next_node after the reversal gives the same bug. Always advance with the saved reference.Pattern 2: Reverse Between (Sublist)
Reversing a sublist uses the identical prev/curr/next reversal loop, but introduces a harder problem: once the segment is reversed, you must stitch it back into the surrounding list without breaking any links. This requires tracking three precise connection points before and after the reversal.
Reverse Between: Three-Point Reconnection
Phase 1: Find PredecessorThe goal: reverse nodes at positions 2 through 4 without disturbing the rest of the list. We need to find the node right before position 2, because that is our anchor for reconnection.
Why dummy handles left=1: When left = 1, the predecessor is position 0, which doesn't exist in the real list. The dummy sits at position 0, so connection = dummy works without a special case.
left steps instead of left - 1, connection lands on the first node of the segment instead of its predecessor. Then connection.next = prev skips a node..next = None (from the reversal). Without tail.next = curr, everything after position right is lost.Pattern 3: Find Middle
slow advances one node per step, fast advances two. When fast reaches the end, slow sits at the middle. The idea is simple, but the loop condition determines which of the two middles you land on for even length lists, and that distinction matters.
Finding the Middle Node
Both pointers start at the head. The 2:1 speed ratio means when fast finishes the list, slow has covered exactly half the distance.
Two loop conditions exist. Choosing the wrong one causes bugs on even length lists:
| Loop Condition | On [1,2,3,4] | Name | Use For |
|---|---|---|---|
| while fast and fast.next | slow → node 3 (second middle) | Second middle | Middle of the Linked List / when the second middle should be returned directly |
| while fast.next and fast.next.next | slow → node 2 (first middle) | First middle | Palindrome, Reorder List, Sort List (slow must be last node of first half before slow.next = None) |
fast.next and fast.next.next. Need slow to be the first node of the second half? Use fast and fast.next.while fast and fast.next for palindrome check means slow overshoots on even lists. You split one node too late and the comparison gets misaligned. Test your chosen variant on [1,2,3,4] and [1,2,3,4,5] before committing.Pattern 4: Floyd's Cycle Detection + Find Start
Floyd's algorithm solves both cycle detection and finding the cycle start in O(n) time and O(1) space. Two phases: first confirm a cycle exists, then locate where it begins.
Floyd's Cycle Detection
Both pointers start at the head. The speed difference of 1 node per step guarantees they will meet inside any cycle.
Step 1 of 8
Phase 1: Detect the Cycle
Fast moves 2 nodes per step, slow moves 1. If there's no cycle, fast reaches None. If there is a cycle, both pointers enter it and fast closes the gap by exactly 1 node per step. It can't skip over slow. Starting gap d means they collide in d steps.
Phase 2: Find the Cycle Start
After the collision, reset one pointer to head and leave the other at the meeting point. Advance both at speed 1. They converge at the cycle start. The math: let a = head to cycle start, b = cycle start to meeting point, c = cycle length. Slow traveled a + b, fast traveled 2(a + b). The extra distance is full cycles: a + b = kc, so a = kc - b. Walking a steps forward from the meeting point goes c - b steps plus full laps, landing exactly at the cycle start.
Pattern 5: Nth From End / Remove Nth
Two pointers with a fixed gap. Advance the leader n + 1 steps ahead, then move both at the same pace. When the leader reaches None, the follower is one node before the target, positioned for the deletion with follower.next = follower.next.next.
Nth From End: Fixed-Gap Two-Pointer
Both pointers start at the dummy. We need a gap of n+1 (not n) because follower must land one node before the target so it can perform the deletion.
Trace for n = 2 on [1,2,3,4,5]:
| Step | leader | follower | Gap |
|---|---|---|---|
| Init | dummy | dummy | 0 |
| Gap 1 | 1 | dummy | 1 |
| Gap 2 | 2 | dummy | 2 |
| Gap 3 | 3 | dummy | 3 |
| Advance 1 | 4 | 1 | 3 |
| Advance 2 | 5 | 2 | 3 |
| Advance 3 | None | 3 | - |
Follower is at node 3. follower.next is node 4 (2nd from end). Delete it: follower.next = follower.next.next gives [1,2,3,5].
Pattern 6: Merge Two Sorted Lists
This pattern shows up standalone and as the merge step inside merge sort. A dummy head starts the result, and a tail pointer tracks the end of what you've built so far. Each step: compare the two heads, append the smaller one to tail, advance that list's pointer.
Merging Sorted Lists
Compare 1 vs 2. Both lists are sorted so the global minimum is always at one of the two heads. Take 1.
tail.next = l1 if l1 else l2 after the loop is the most forgotten line in merge implementations. Without it, whichever list still has nodes gets silently dropped.Compositions (Recipes)
Each problem below uses two or three of the patterns covered above. The code for each operation is already written. The work is seeing which ones apply and in what order.
Reorder List
[1→2→3→4→5] → [1→5→2→4→3]
Three operations: find middle (first middle variant), reverse the second half, interleave the two halves.
Reorder List: Three-Phase Decomposition
Reorder requires three phases: find middle, reverse second half, then interleave. Start by locating the midpoint with fast/slow pointers.
Palindrome Linked List
Check if a linked list reads the same forward and backward. O(n) time, O(1) space.
Three operations: find middle (first middle variant), reverse the second half, compare node by node. Optionally restore the list afterward.
Same slow.next = None cut as Reorder List. The compare loop uses while p2 because the second half is equal or shorter than the first on odd length lists.
Sort List
Merge sort a linked list. O(n log n) time, O(log n) space (recursion stack).
Four operations: find middle (first middle variant), split into two independent lists, recursive sort each half, merge the sorted results.
The critical cut slow.next = None splits the list into two independent lists. Without it, the recursive call on head still reaches into the second half, causing infinite recursion. Base case: a single node or None is already sorted.
When These Techniques Break
Each technique has assumptions. Knowing where they fail tells you when to reach for a different approach.
Random access is needed
If the problem requires looking up nodes by index repeatedly, a linked list is the wrong structure. Arrays give O(1) access by index. Linked list traversal is O(n) per lookup. A problem that indexes into the list frequently is better solved with an array or deque.
Backward traversal is needed repeatedly
A singly linked list only traverses forward. If the problem requires stepping backward at multiple points, a doubly linked list or a stack to store previous nodes is usually cleaner than re-traversing from the head each time.
Reversal is destructive
Iterative reversal rewires every pointer in the list. The original order no longer exists after it runs. If the list must be returned in its original state, you must reverse it a second time afterward. Problems that allow input modification (palindrome checking in most interview settings) accept the destruction. If the problem explicitly requires the input to be unchanged, reversal must be followed by a second reversal to restore order.
Recursion depth
Recursive reversal and recursive merge sort both use O(n) stack space for call frames. On very long lists, this overflows the call stack. The iterative equivalents for reversal and merge both use O(1) space and should be preferred unless recursion is specifically requested or the list is guaranteed short.
Merge sort is not truly O(1) space in the recursive form
The recursive merge sort in this guide uses O(log n) stack space for the recursive call frames. It is not strictly O(1) space. Truly constant-space merge sort requires a bottom-up iterative approach that merges fixed-size sublists in passes. This is significantly harder to implement and is rarely required in interviews, but is worth knowing the distinction if asked.
Fast/slow assumes a linear structure
The convergence proofs for cycle detection and middle-finding assume a one-directional chain with no branching. A tree or any structure where a node has multiple next pointers breaks both techniques. When working on trees, use DFS or BFS rather than the fast/slow pointer approach.
Debugging Linked List Code
When a linked list solution produces a wrong answer or crashes, work through these questions before rereading the problem. Most bugs fall into one of seven categories.
Did you save next_node = curr.next before setting curr.next = prev? Without this, everything past curr is permanently unreachable.
After finding the middle, did you set slow.next = None? Without the cut, the first half still reaches into the second half and the two lists are not independent.
After the merge loop, did you attach the remaining list with tail.next = l1 if l1 else l2? Whichever list runs out last still has nodes. Without this line, they are silently dropped.
Which fast/slow loop condition did you use? while fast and fast.next lands on the second middle; while fast.next and fast.next.next lands on the first. Trace both on a 4-node list to confirm which your problem needs.
After Reverse Between, did you set both connection.next = prev and tail.next = curr? Missing either reconnection severs the list at that boundary.
Are you returning dummy.next and not dummy or head? The dummy node is the sentinel, not part of the result.
After the reversal loop, what does each variable point to? prev is the new head and curr is None. If code after the loop expects otherwise, the loop exited one step early or late.
Practice Problems
Reversal
| Problem | Difficulty | Approach |
|---|---|---|
| Reverse Linked List | Easy | Keep three pointers: prev, curr, next. Each step points curr.next back to prev, then shifts all three forward. Return prev when curr hits null. O(n) time, O(1) space. |
| Reverse Linked List II | Medium | Walk to position left minus 1 using a dummy node. Reverse the sublist from left to right with the three pointer technique, then stitch the boundaries back together. |
| Reverse Nodes in k-Group | Hard | Count k nodes ahead. If fewer than k remain, leave them alone. Otherwise reverse the next k nodes as a group and recurse on the rest. Dummy node keeps the head clean. |
| Swap Nodes in Pairs | Medium | Use a dummy node. For each pair, rewire the two nodes and advance the pointer by two. Stop when fewer than two nodes remain (handles odd length). |
Fast-Slow
| Problem | Difficulty | Approach |
|---|---|---|
| Middle of the Linked List | Easy | Move slow one step, fast two steps. When fast reaches the end, slow is at the middle. For even length lists this gives the second of the two middle nodes. |
| Linked List Cycle | Easy | Advance slow by one, fast by two. If they ever meet, there is a cycle. If fast hits null, there is no cycle. |
| Linked List Cycle II | Medium | After detecting the meeting point, reset one pointer to head. Move both one step at a time. They meet at the cycle entrance. Math: the distance from head to entrance equals the distance from meeting point to entrance around the cycle. |
| Happy Number | Easy | Treat the sequence of digit square sums as a linked list. Use fast slow to detect a cycle. If the cycle includes 1, the number is happy. Otherwise it loops forever. |
Merge & Rearrange
| Problem | Difficulty | Approach |
|---|---|---|
| Merge Two Sorted Lists | Easy | Dummy head, compare fronts, append the smaller node and advance that pointer. When one list runs out, attach the other. O(n+m) time. |
| Remove Nth Node From End | Medium | Two pointers with a gap of n nodes. When the lead hits the end, the trailer is right before the target. Dummy node handles removing the head. |
| Merge k Sorted Lists | Hard | Push the head of each list into a min heap. Pop the smallest, append it, push its next node. Repeat until the heap is empty. O(N log k) where N is total nodes. |
Compositions
| Problem | Difficulty | Approach |
|---|---|---|
| Reorder List | Medium | Find middle with fast slow, reverse the second half, then interleave nodes from both halves by alternating next pointers. Three classic operations composed into one. |
| Palindrome Linked List | Medium | Find middle, reverse second half, compare both halves node by node. Optionally restore the list afterward. O(n) time, O(1) space. |
| Sort List | Medium | Split at the middle using fast slow, recursively sort each half, merge with the standard merge technique. O(n log n) time, O(log n) stack space. |
| Add Two Numbers II | Medium | Reverse both lists so digits go from ones place up. Add digit by digit with carry using the standard addition loop. Reverse the result to restore original order. |
Reference Templates
Use this section to recover the code shapes without rereading the full guide.
Iterative Reversal
Use when every pointer in the list must be redirected.
Find Middle: Second Middle
Use when a problem needs the start of the second half (merge sort).
Find Middle: First Middle
Use when the problem splits the list and needs slow as the last node of the first half (palindrome, reorder).
Floyd's Cycle Detection + Cycle Start
Use when loop structure must be detected in O(1) space.
Remove Nth From End
Use when the deletion target is defined relative to the tail.
Merge Two Sorted Lists
Use when both input lists are already sorted.
Reverse Between
Use when only a bounded segment should be reversed.
Pattern Recap
- Iterative reversal uses three pointers.
next_nodemust be saved beforecurr.nextis overwritten. After the loop,previs the new head andcurris None. - Finding the middle uses two pointers at different speeds. The loop condition determines which of the two middles is returned for even-length lists. Verify on a 4-node example before committing to a condition.
- Floyd's detection works because fast closes the gap by exactly 1 per step once both pointers are inside the cycle. The cycle-start phase exploits the distance symmetry: the remaining distance from the meeting point to the cycle start equals the distance from head to the cycle start.
- The n+1 gap in Nth From End positions the follower at the predecessor of the target, not the target itself. A gap of n lands one step too late for deletion.
- Merge needs
tail.next = l1 if l1 else l2after the loop. The dummy eliminates the empty-result special case and makes every append uniform. - All three compositions (Reorder, Palindrome, Sort) begin with find middle and sever the first half with
slow.next = None. The third step differs per problem: interleave, compare, or merge.
Rebuilding the Pattern
When a linked list problem feels unclear, start with the operations it requires. A problem that asks for ordered manipulation after splitting always begins with find middle. A problem that asks for structure detection without extra space is almost always fast/slow. A problem that involves sorted output from a linked list is merge or merge sort. Identifying the required operations first makes the implementation straightforward because each operation has a fixed, short template.
After identifying the operations, check pointer safety for each one. Every bug in a linked list solution comes from one of three sources: overwriting a pointer before saving the forward reference, failing to sever the link when splitting a list into two independent halves, or losing the remainder when a merge loop exits before one list is exhausted. Getting those three checks right in the correct order is the whole skill.
Check Your Understanding
Use these questions to check whether you can reason through the operations without looking at the template.
Ready to test it?
12 questions across reversal, fast-slow, cycle detection, and merging.
Practice this pattern
Apply the guide to complete interview problems with explanations and code.
Learn Linked Lists in a guided sequence
The Interview Course connects this pattern to its prerequisites, worked lessons, and progressively harder problems.