Pattern 09 of 22
Linked List Pattern: Template + 75 LeetCode Problems
Rewire pointers in place, with a dummy head and a saved next to keep it safe.
- Easy
- 12
- Medium
- 56
- Hard
- 7
- Time
- O(n)
What the linked list pattern is
Linked list problems are pointer-rewiring exercises, and nearly all of the difficulty is in the edge cases rather than the algorithm. Two habits remove most of them. First, allocate a dummy node in front of the real head whenever the head itself might be deleted or replaced, so the head stops being a special case and the answer is always `dummy.next`. Second, before overwriting any `next`, save it — the reversal loop is exactly the three-step dance of saving the successor, redirecting the current node backwards, and stepping both cursors forward. The other half of the pattern is fast-and-slow pointers: advancing one cursor two nodes for every one of the other's finds the midpoint in a single pass, detects a cycle when the two meet, and locates the cycle's entry point when a third walk starts from the head. In-place work keeps the space at O(1), which is usually the actual constraint being tested.
When to use it
- Nodes must be reordered, reversed, merged or removed without allocating a new list.
- The head of the list can change — that is the dummy node's cue.
- A cycle, a midpoint, or the nth node from the end is wanted in one pass.
- The problem forbids converting the list to an array, which is otherwise always tempting.
The linked list template in Python
The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 75 problems listed below.
def reverse(head):
previous = None
node = head
while node:
following = node.next # save it before the link is destroyed
node.next = previous # rewire backwards
previous = node # step both cursors forward
node = following
return previous # the old tail is the new headComplexity characteristics
- Time
- O(n)
- Auxiliary space
- O(1)
One pass, rewiring pointers as it goes. The constant space is the entire point of the pattern and is usually the constraint being tested — copying the list into an array makes almost all of these problems trivial at O(n) space, which is why the statement so often forbids it. Fast-and-slow pointers hold both figures: the midpoint, a cycle check and the nth node from the end each cost one pass and two pointers.
Eyes only
Meet the linked list problem you did not practise.
In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.
All 75 linked list LeetCode problems
Every problem in the library the linked list pattern applies to, grouped by LeetCode's own difficulty rating. 63 of the 75 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.
Related LeetCode topics
Easy (12)
| No. | Problem | Topics |
|---|---|---|
| 0021 | Merge Two Sorted Lists | |
| 0083 | Remove Duplicates from Sorted List | |
| 0141 | Linked List Cycle | |
| 0160 | Intersection of Two Linked Lists | |
| 0203 | Remove Linked List Elements | |
| 0206 | Reverse Linked List | |
| 0234 | Palindrome Linked List | |
| 0705 | Design HashSet | |
| 0706 | Design HashMap | |
| 0876 | Middle of the Linked List | |
| 1290 | Convert Binary Number in a Linked List to Integer | |
| 1474 | Delete N Nodes After M Nodes of a Linked ListPremium |
Medium (56)
Hard (7)
| No. | Problem | Topics |
|---|---|---|
| 0023 | Merge k Sorted Lists | |
| 0025 | Reverse Nodes in k-Group | |
| 0432 | All O`one Data Structure | |
| 0460 | LFU Cache | |
| 0716 | Max StackPremium | |
| 1206 | Design Skiplist | |
| 2296 | Design a Text Editor |
Linked List pattern FAQ
What is the linked list pattern?
Linked list problems are pointer-rewiring exercises, and nearly all of the difficulty is in the edge cases rather than the algorithm. Two habits remove most of them.
How many LeetCode problems use the linked list pattern?
This page lists 75 LeetCode problems that the linked list pattern applies to: 12 Easy, 56 Medium and 7 Hard. 63 of them carry a complete Python solution with complexity analysis.
What is the time complexity of the linked list pattern?
O(n) time and O(1) space. One pass, rewiring pointers as it goes. The constant space is the entire point of the pattern and is usually the constraint being tested — copying the list into an array makes almost all of these problems trivial at O(n) space, which is why the statement so often forbids it. Fast-and-slow pointers hold both figures: the midpoint, a cycle check and the nth node from the end each cost one pass and two pointers.
When should I use the linked list pattern in an interview?
Nodes must be reordered, reversed, merged or removed without allocating a new list. The head of the list can change — that is the dummy node's cue.
Which linked list problem should I start with?
LeetCode 21. Merge Two Sorted Lists is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.
What patterns are related to linked list?
Two Pointers, Hash Map, Tree Traversal, Sorting. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.
More ways in: all 22 patterns, the curated study lists, or the full problem list.