~20 minutes · prev/curr/next · Python
Tonight's linked-list problem is Reverse Linked List. Interviewers love it because it is small, visual, and unforgiving: one pointer update in the wrong order can lose the rest of the list. The win is learning a safe order you can say out loud before you code.
Reversal is re-aiming one arrow per step; save next before you break the link so you don't lose the rest.
A singly linked list is a chain of nodes where each node points to the next one (Wikipedia: linked list). Reversing the list does not require new nodes. It requires changing each next arrow so it points backward instead of forward.
The brute-force version is to copy every node into an array, then reconnect those nodes from right to left. It is O(n) time and O(n) space:
def reverse_list(head):
nodes = []
cur = head
while cur:
nodes.append(cur)
cur = cur.next
for i in range(len(nodes) - 1, 0, -1):
nodes[i].next = nodes[i - 1]
nodes[0].next = None
return nodes[-1]
This works, but the array is the crutch. The interview version wants the same O(n) time with O(1) extra space: keep only three names — prev, curr, and nxt — and move the boundary one node at a time. The LeetCode statement defines the target behavior here: return the head of the reversed list (LeetCode: Reverse Linked List).
At any moment, prev is the head of the reversed prefix, and curr is the first node not fixed yet. Save curr.next before changing it, because that arrow is your only path to the untouched suffix.
One loop step: protect the untouched suffix with nxt, then turn curr's arrow around.
def reverseList(head):
prev, curr = None, head
while curr:
nxt = curr.next # save the untouched suffix
curr.next = prev # re-aim this arrow backward
prev = curr # grow the reversed prefix
curr = nxt # move to the next untouched node
return prev # new head
Trace three nodes on paper: 1 → 2 → 3. After the first loop, 1 points to None. After the second, 2 → 1. After the third, 3 → 2 → 1. The code is short because the invariant is doing the work.
Palindrome Linked List often uses this same primitive: find the middle, reverse the second half, then compare both halves.
Before opening the reveal: if the second half starts at slow, what helper should you call, and what must be true while it runs? Say the invariant out loud first.
Call the same reversal helper on slow. While it runs, prev is the reversed prefix of the second half, curr is the first untouched node, and nxt preserves the rest before each arrow changes.
| Approach | Time | Space |
|---|---|---|
| Array reconnect | O(n) | O(n) |
| prev/curr/next pointers | O(n) | O(1) |
The speed is the same. The difference is control: the pointer version keeps the whole operation in the list itself.
1. What must you save before changing curr.next?
curr.next points backward, the old forward arrow is gone.2. After one loop step, what does prev point to?
prev is always the head of the reversed prefix. That prefix grows by one node each loop.3. Spot the bug in this loop:
while curr:
curr.next = prev
nxt = curr.next
prev = curr
curr = nxtnxt after overwriting curr.next. At that point, the original rest of the list is no longer reachable.4. Which future task uses this same primitive?
Solve Reverse Linked List in your Notion tracker with the cycle — predict → attempt → compare → encode.
1 → 2 → 3, name prev, curr, and nxt, then state the invariant.Watch NeetCode — Reverse Linked List after your attempt, as the compare step. Listen for the moment he saves the next pointer before redirecting the current one.