Algorithms
Linked List Algorithms
Difficulty: Intermediate
Reversing a singly linked list is a four-line iteration with three pointers (prev, curr, next), and yet roughly a third of candidates implement it incorrectly under interview pressure. The reason is that linked-list problems give you no...
Linked List Algorithms
Reversing a singly linked list is a four-line iteration with three pointers (prev, curr, next), and yet roughly a third of candidates implement it incorrectly under interview pressure. The reason is that linked-list problems give you no random access: every operation has to be expressed as careful, ordered pointer rewrites, and one missed assignment loses the rest of the list forever.
Linked List Algorithms is the lesson where pointer manipulation becomes a reliable skill. You will reverse a list iteratively and recursively, then extend the technique to reverse in groups of k. You will use Floyd's fast and slow pointers to detect cycles, find the cycle start, locate the middle element, and check whether a list is a palindrome. You will merge two sorted lists, then merge k sorted lists with a min-heap. The lesson also covers removing the nth node from the end, finding the intersection of two lists, deep-copying a list with random pointers, and the dummy-node trick that eliminates head-edge cases entirely.
In Linked Lists (Singly), you saw how nodes and next pointers form a list and why insertion at a known position is O(1). Two Pointers (Intro) introduced fast and slow indices on arrays; this lesson reuses the same idea on pointer-linked nodes.
Next, Tree Algorithms generalizes pointer-and-recursion thinking to branching structures.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Reverse a singly linked list using the iterative three-pointer technique.
Use Floyd's fast/slow pointers to detect a cycle and find the cycle start.
Merge two sorted linked lists into one sorted list.
Apply the dummy node technique to simplify linked list operations.
Find the middle of a linked list using the fast/slow pointer technique.
Remove the nth node from the end using the two-pointer gap technique.
Why This Matters
01
Linked list problems are among the most common interview questions at top companies because they test precise pointer manipulation under pressure.
02
Floyd's fast/slow pointer technique extends beyond linked lists to arrays (finding duplicate numbers) and mathematical sequences.
03
Reversing a linked list is a building block for many harder problems: reverse in groups of k, palindrome check, and reorder list.
04
The dummy node technique eliminates edge cases when inserting or removing at the head, making code cleaner and less error-prone.
Key Terms
6 terms you'll encounter in this lesson
Three-pointer reversal
The iterative technique for reversing a linked list using prev, curr, and next pointers. At each step, curr.next is redirected to prev.
Floyd's algorithm
A cycle detection algorithm using two pointers moving at different speeds. If they meet, a cycle exists. Also known as the tortoise and hare algorithm.
Fast/slow pointers
Two pointers where fast moves 2 steps and slow moves 1 step per iteration. They meet inside a cycle, and slow reaches the middle when fast reaches the end.
Dummy node
A sentinel node placed before the head of a list to eliminate edge cases. The actual result starts at dummy.next.
Runner technique
Using a pointer that starts ahead or moves faster than another to create a fixed gap. Used for finding the nth-from-end node.
In-place reversal
Reversing the list by changing next pointers without allocating new nodes. Uses O(1) extra space.
Heads Up
Common misconceptions to watch out for
"You need extra space to reverse a linked list"
Iterative reversal uses only three pointers (prev, curr, next) and reverses in O(1) space by redirecting next pointers.
"Fast/slow pointers always meet at the cycle start"
They meet somewhere inside the cycle, not necessarily at the start. To find the cycle start, reset one pointer to the head and advance both at the same speed until they meet again.
"The dummy node wastes memory"
The dummy node is a single temporary node that greatly simplifies code by eliminating special cases for head insertion/deletion. It is freed after use.