Linked List
The Linked List Pattern
Pointer manipulation with no random access. Almost every linked list technique is one of three moves: run two pointers at different speeds, reverse a section in place, or use a dummy head so the first node needs no special case.
Interactive problems
Free to open
How do you recognise a linked list problem?
The input is a list rather than an array, and the question asks about cycles, the nth node from the end, reordering, or comparing the list against itself. The giveaway constraint is "do it in one pass" or "use O(1) extra space" — both rule out copying into an array.
What is the time complexity of the linked list pattern?
O(n) time and O(1) extra space for the pointer techniques. Copying into an array also gives O(n) time but costs O(n) space, which is usually the thing being tested.
Linked List practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Linked List problems by difficulty and complexity
The difficulty, running time and extra space of every linked list solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Linked List Overview | Easy | Ω(n) | Θ(n) | O(n) | O(1) |
| Reverse Linked List | Easy | Ω(n) | Θ(n) | O(n) | O(1) |
| Merge Two Sorted Lists | Easy | Ω(min(n, m)) | Θ(n + m) | O(n + m) | O(1) |
| Linked List Cycle | Easy | Ω(1) | Θ(n) | O(n) | O(1) |
| Palindrome Linked List | Easy | Ω(n) | Θ(n) | O(n) | O(1) |
| Remove Nth Node From End of List | Medium | Ω(n) | Θ(n) | O(n) | O(1) |
| Reorder List | Medium | Ω(n) | Θ(n) | O(n) | O(1) |
| Swap Nodes in Pairs | Medium | Ω(n) | Θ(n) | O(n) | O(1) |
Related patterns and concepts
The underlying technique is covered from first principles in the linked list lesson in the DSA visualizer curriculum. Linked List is one of the 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Depth-First Search · 25 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Construct Binary Tree from Preorder and Inorder Traversal
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree