Three pointers, four lines, one loop. Every list-surgery question in an interview is this loop wrapped in bookkeeping.
Reversing a linked list is the most-asked warm-up in the business, and the harder versions, reverse a sublist, reverse in groups of k, rotate, reorder, are the same four lines with more careful stitching at the boundaries. Learn the loop until you can write it without thinking, then spend your attention on the joins.
| Signal | What it looks like |
|---|---|
| Reversal language | “reverse”, “in reverse order”, “flip the direction”. |
| Partial reversal | “between positions left and right”, “in groups of k”, “every other node”. |
| Rearrangement | “reorder the list”, “is it a palindrome”, “rotate by k”. These all reverse a half or a suffix as a step. |
| Space constraint | “O(1) memory”, “without allocating new nodes”, “do not change the values”. |
prev, the part already reversed; current, the node being flipped; and nxt, a saved copy of the rest. Each iteration does exactly one thing, point current.next backwards at prev, and then shuffles all three forward one place. The saved nxt exists only because the assignment destroys the forward link you still need.current is None.current are already reversed and prev is their head; the nodes from current on are still in the original order. When current becomes None, the first half is the whole list, so prev is the new head. That last sentence is why the function returns prev, not head, and it is the detail people fumble.Partial-reversal problems change the head sometimes and not other times, and that conditional makes the code messy. A dummy node in front of the real head removes the special case entirely.
dummy = ListNode(0, head) # a node that is not part of the data
# ... do all the surgery, treating dummy as an ordinary predecessor ...
return dummy.next # whatever ended up first is the real head
from dataclasses import dataclass
@dataclass
class ListNode:
"""A singly linked list node."""
val: int = 0
next: "ListNode | None" = None
def reverse(head: ListNode | None) -> ListNode | None:
"""Return the head of the reversed list."""
prev: ListNode | None = None
current = head
while current is not None:
nxt = current.next # 1. save the rest before destroying the link
current.next = prev # 2. flip
prev = current # 3. advance prev
current = nxt # 4. advance current
return prev # current is None, so prev is the new head
Always in this order. Steps 3 and 4 read strangely because prev takes the old current, which is why writing them as a Python tuple assignment is tempting and also easy to get wrong. Write the four lines.
def reverse_n(before: ListNode, n: int) -> None:
"""Reverse the n nodes after `before`, in place, restitching both ends."""
tail = before.next # the block's first node becomes its last
prev: ListNode | None = None
current = tail
for _ in range(n):
nxt = current.next
current.next = prev
prev = current
current = nxt
before.next = prev # front joint: point at the new first node
tail.next = current # back joint: old first node now leads the rest
The two joints at the end are the entire difficulty of every partial-reversal problem. Name them front joint and back joint and draw them before you code.
head instead of prev. After a full reversal head is the last node.current.next before saving it strands everything downstream. Save first, always.while current: on a node whose val is falsy. A dataclass without __bool__ is fine, but is not None states the intent and never surprises you.Given the head of a singly linked list, reverse it and return the new head.
def reverse_list(head: ListNode | None) -> ListNode | None:
"""Reverse a singly linked list in place.
Args:
head: First node, or None for an empty list.
Returns:
The head of the reversed list, which is the original last node.
Example:
1 -> 2 -> 3 -> None becomes 3 -> 2 -> 1 -> None
"""
prev: ListNode | None = None
current = head
# Invariant: everything before `current` is reversed, headed by `prev`.
while current is not None:
nxt = current.next
current.next = prev
prev = current
current = nxt
return prev
def reverse_list_recursive(head: ListNode | None) -> ListNode | None:
"""Same result, expressed as a recursion.
The recursion reverses the tail first, then attaches head to its end.
"""
if head is None or head.next is None:
return head # empty or single node: already done
new_head = reverse_list_recursive(head.next)
# head.next is the tail of the reversed remainder; make it point back.
head.next.next = head
head.next = None
return new_head
1 → 2 → 3 → None:
| step | prev | current | list so far |
|---|---|---|---|
| start | None | 1 | 1 → 2 → 3 |
| 1 | 1 | 2 | 1 → None, rest 2 → 3 |
| 2 | 2 | 3 | 2 → 1, rest 3 |
| 3 | 3 | None | 3 → 2 → 1 |
prev is None, correct.next becomes None, returns itself.next must end up None. The first iteration does that, because prev starts at None. Point this out.prev, not head, because when the loop ends current is None and prev is sitting on the last node I flipped.”Reverse the nodes of a list from position left to position right, 1-indexed and inclusive, and return the head. Do it in one pass.
left, the block to reverse, the suffix after right. Only the block moves; the two joints must be restitched.left == 1 needs no special case.left. Call it before. Remember before.next as tail, because after the reversal the block’s first node is its last.right - left + 1 times, then make the two joints.def reverse_between(
head: ListNode | None, left: int, right: int
) -> ListNode | None:
"""Reverse the sublist from 1-indexed position left to right, inclusive.
Args:
head: First node.
left: Start position, 1-indexed.
right: End position, 1-indexed, with left <= right.
Returns:
The head of the modified list.
Example:
1 -> 2 -> 3 -> 4 -> 5, left=2, right=4 becomes 1 -> 4 -> 3 -> 2 -> 5
"""
if head is None or left == right:
return head
dummy = ListNode(0, head)
# Step 1: walk to the node just before the block.
before = dummy
for _ in range(left - 1):
before = before.next
# Step 2: reverse exactly (right - left + 1) nodes.
tail = before.next # first node of the block, the future tail
prev: ListNode | None = None
current = tail
for _ in range(right - left + 1):
nxt = current.next
current.next = prev
prev = current
current = nxt
# Step 3: the two joints. prev is the block's new head,
# current is the first node after the block.
before.next = prev
tail.next = current
return dummy.next
1 → 2 → 3 → 4 → 5 with left = 2, right = 4:
| Step | State |
|---|---|
| after step 1 | before is node 1 |
| after step 2 | tail is node 2, prev is node 4, current is node 5; block reads 4 → 3 → 2 |
| front joint | 1.next = 4 |
| back joint | 2.next = 5 |
Result 1 → 4 → 3 → 2 → 5.
left == 1: before stays on the dummy, and dummy.next delivers the new head. This is exactly why the dummy is there.left == right: guarded and returned untouched.right == n: current ends as None, and the back joint correctly terminates the list.left = 1, right = 2: a good quick trace before you say you are done.Reverse the nodes of a list k at a time and return the modified list. If the number of remaining nodes is fewer than k, leave them as they are. You may not change the values, only the links.
k nodes, because a short final group is left alone.k steps from group_prev to find kth, the last node of the group. If that walk hits None, the tail is short and you are finished.group_next rather than at None. Seeding prev = group_next makes the back joint happen for free inside the loop, which removes one of the two stitches.group_prev for the next round. Capture it before you overwrite group_prev.next.def reverse_k_group(head: ListNode | None, k: int) -> ListNode | None:
"""Reverse the list in consecutive groups of k, leaving a short tail as is.
Args:
head: First node.
k: Group size, k >= 1.
Returns:
The head of the modified list.
Example:
1 -> 2 -> 3 -> 4 -> 5, k=2 becomes 2 -> 1 -> 4 -> 3 -> 5
"""
if k <= 1 or head is None:
return head
dummy = ListNode(0, head)
group_prev = dummy
while True:
# Look ahead k nodes. If we run out, the remaining tail stays put.
kth = group_prev
for _ in range(k):
kth = kth.next
if kth is None:
return dummy.next
group_next = kth.next
# Reverse the group. Seeding prev with group_next means the group's
# old head ends up pointing at the rest of the list automatically.
prev, current = group_next, group_prev.next
while current is not group_next:
nxt = current.next
current.next = prev
prev = current
current = nxt
# group_prev.next is still the group's OLD head, now its tail.
new_group_prev = group_prev.next
group_prev.next = kth # front joint: kth is the group's new head
group_prev = new_group_prev
prev = group_nextprev starts at None so the first node flipped ends up terminating the list. Here the group is in the middle, so the first node flipped should point at whatever follows the group. Seeding prev with group_next does exactly that on the very first iteration, so the back joint is already correct when the loop ends. One less thing to remember, and one less place to get it wrong.1 → 2 → 3 → 4 → 5 with k = 2:
| Round | Look-ahead | After the group |
|---|---|---|
| 1 | kth = node 2, group_next = node 3 | 2 → 1 → 3 → 4 → 5, group_prev = node 1 |
| 2 | kth = node 4, group_next = node 5 | 2 → 1 → 4 → 3 → 5, group_prev = node 3 |
| 3 | walk hits None after one step | return; node 5 is left alone |
Each node is visited at most twice, once by a look-ahead and once by a reversal, so the total is linear despite the nested loops.
k == 1: guarded, returns the list unchanged. Without the guard the loop still works but does pointless work.k >= n: the first look-ahead may fail, and the whole list is returned untouched, or reversed exactly once if k == n.k: the short tail survives in original order, which is the requirement.None. Small change, completely different code path. Confirm which variant is wanted before writing anything.prev with the node after the group so the back joint is made inside the loop instead of after it.”prev, advance current.prev. When current reaches None, prev is the new head.current is reversed and headed by prev.That closes the pointer patterns. Pattern 7, Breadth-First Search, moves to trees and graphs, where the state you carry is a whole queue rather than two or three references, and where the shape of the traversal is the answer.