Builds on Dummy Node, which you haven’t finished yet.
In-Place Linked List Reversal (Reverse Linked List II, Reverse Nodes in k-Group)
You get head, the first node of a singly linked list. Each node holds a value val and a pointer next to the node after it; the last node's next is None, and an empty list has head = None.
Turn the list around: the node that was last must come first, and every node must point to the one that used to come before it. Return the first node of the reversed list (None for an empty list, written []).
Follow-up: once you have one version, write the other one too, a loop and a recursive function.
5, the old last node, is the new head and 1 ends the list.Linked List Reversal
head ➔ rewire each next pointer ➔ reversed list| 1 | from typing import Optional |
| 2 | |
| 3 | |
| 4 | class ListNode: |
| 5 | def __init__(self, val: int = 0, next: Optional["ListNode"] = None): |
| 6 | self.val = val |
| 7 | self.next = next |
| 8 | |
| 9 | |
| 10 | def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]: |
| 11 | """Reverse Linked List: flip every next pointer in one pass. |
| 12 | Time: O(N) | Space: O(1) |
| 13 | """ |
| 14 | prev = None # Head of the reversed part: empty at the start |
| 15 | curr = head # First node not flipped yet |
| 16 | while curr: |
| 17 | nxt = curr.next # Save the rest BEFORE the flip overwrites curr.next |
| 18 | curr.next = prev # Flip: curr now points back at the reversed part |
| 19 | prev = curr # The reversed part grows by one node |
| 20 | curr = nxt # Step into the saved rest |
| 21 | return prev # The old tail is the new head |
| 22 | |
| 23 | |
| 24 | def reverse_between(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: |
| 25 | """Reverse Linked List II: reverse positions left..right (1-indexed) in one pass. |
| 26 | Time: O(N) | Space: O(1) |
| 27 | """ |
| 28 | dummy = ListNode(0, head) # The segment may start at the head: give it a node before it |
| 29 | before = dummy |
| 30 | for _ in range(left - 1): # Walk to the node just before position left |
| 31 | before = before.next |
| 32 | prev = None |
| 33 | curr = before.next |
| 34 | for _ in range(right - left + 1): # The same flip, exactly right - left + 1 times |
| 35 | nxt = curr.next |
| 36 | curr.next = prev |
| 37 | prev = curr |
| 38 | curr = nxt |
| 39 | tail = before.next # The segment's old first node is now its last |
| 40 | before.next = prev # Reattach the reversed segment... |
| 41 | tail.next = curr # ...and hang the untouched rest behind it |
| 42 | return dummy.next |
prev heads the nodes already reversed and curr heads the nodes not touched yet: every node is in exactly one of the two lists.Reversing a singly linked list only needs every next pointer to point the other way, so walk the list once with two pointers: prev heads the part already reversed (it starts as None) and curr is the first node not flipped yet; each step points curr.next back at prev, then moves prev and curr one node forward. Each step moves exactly one node from the front of the untouched part to the front of the reversed part, so no node is lost or visited twice, and when curr falls off the end, prev is the new head. reverse_between runs the same steps right - left + 1 times from the node before position left, then reconnects both ends with before.next = prev and tail.next = curr. The trap is the order of the lines: curr.next = prev overwrites the only link to the rest of the list, so save nxt = curr.next first; flip first and every node after curr is lost.
See it run
Linked list reversal, head = [1, 2, 3, 4, 5]
prev Nonecurr 1
Each circle is a node and each arrow is its next link. The arrows change direction one node at a time.
prevthe head of the part that is already reversedcurrthe node whose link is flipped nownxtthe saved rest of the listnew linkthe link that was just flippedlostnodes that no variable and no link reaches any more
prev is None and curr is the head, node 1. Every link still points forward.
Gotcha 1 of 4
- The trap
Gotcha 1: Writing
curr.next = prevbefore savingnxtMistakewhile curr: curr.next = prev nxt = curr.nextFixwhile curr: nxt = curr.next curr.next = prevWhat happens:
curr.nextis the only link fromcurrto the rest of the list.curr.next = prevoverwrites that link. Thennxt = curr.nextsavesprev, which isNoneon the first step. The loop ends after one node, and every node aftercurris lost.Example: head = [1, 2, 3]Mistake: returns [1]Fix: returns [3, 2, 1]
- The data is an array you can index, as in Rotate Array (LC 189): reverse by swapping values from both ends of a range, not by rewiring
nextpointers. See Three-Reversals Algorithm
Deep Dive
Why every node moves from one list to the other
A singly linked list stores one pointer per node, next. Reversing the list means that every next points the other way. The old tail becomes the head, and the old head points at None.
The loop keeps two lists. prev is the head of the part that is already reversed. It starts as None, which is an empty list. curr is the head of the part that is not touched yet. It starts as head. Every node is in exactly one of the two lists.
One round does four things. nxt = curr.next saves the rest of the untouched part. curr.next = prev makes curr point at the reversed part. prev = curr makes curr the new head of the reversed part. curr = nxt steps into the saved rest. So one round moves exactly one node from the front of the untouched list to the front of the reversed list.
Trace head = [1, 2, 3, 4, 5] from Reverse Linked List (LC 206). After round 1, the reversed list is 1 and the untouched list is 2, 3, 4, 5. After round 2, the reversed list is 2, 1. After round 5, the reversed list is 5, 4, 3, 2, 1 and curr is None, so the loop stops. prev is the new head.
Each node is moved once, and each round does a fixed number of steps. So the loop takes N rounds. An empty list never enters the loop, and return prev returns None.
Why nxt must be saved before the flip
curr.next is the only link from curr to the rest of the list. The line curr.next = prev overwrites that link. After it, no variable and no pointer reaches the nodes behind curr.
Look at the trap step on the board. Suppose the code runs curr.next = prev first. For the head 1, prev is None, so node 1 now points at None. Then nxt = curr.next saves None, not node 2. The loop sets curr = None and stops after one round. The nodes 2, 3, 4, 5 still point at each other, but nothing points at node 2. They are lost, and the function returns a list with one node.
The correct order is: save, flip, move prev, move curr. The save must come first because it reads the link that the flip destroys.
A second mistake is return head. When the loop ends, the old head is the tail. Its next is None, so returning it gives a list with one node. The new head is prev.
Reversing only the positions from left to right
Reverse Linked List II (LC 92) reverses the nodes from position left to position right and keeps the others. reverse_between runs the same four lines, but only right - left + 1 times, and then it reconnects both ends.
Trace head = [1, 2, 3, 4, 5] with left = 2 and right = 4. dummy is a node placed before the head. before starts at dummy and moves left - 1 = 1 time, so before is node 1. prev is None and curr is node 2.
Three rounds flip node 2, node 3 and node 4. Now prev is node 4, the head of the reversed part. curr is node 5, the first node after the segment. Node 2 points at None.
tail = before.next reads node 2, the first node of the segment, which is now its last node. before.next = prev makes node 1 point at node 4. tail.next = curr makes node 2 point at node 5. The result is [1, 4, 3, 2, 5].
tail must be read before before.next = prev runs, because that line overwrites the only link to node 2. dummy is needed for left = 1. Then no real node is before the segment, and dummy.next is what the function returns.
Cost and the problems that reuse the flip
Both functions take O(N) time, because each node is visited a constant number of times. They take O(1) space: three pointers and, in reverse_between, dummy, before and tail. A recursive version needs O(N) space for the call stack.
Palindrome Linked List (LC 234) finds the middle, reverses the second half in place and compares the two halves node by node. Reorder List (LC 143) also reverses the second half, and then it takes one node from each half in turn.
Reverse Nodes in k-Group (LC 25) uses the reverse_between steps for each group of k nodes. A counting loop checks first that k nodes remain. A last group with fewer than k nodes stays as it is. Without that check, the flip loop would reverse the short group as well.
If you can index the data, as with an array, do not rewire anything. Swap values from both ends instead, as the Three-Reversals Algorithm card does.
60-Second Pitch
"I reverse the list in place with two pointers. prev heads the part that is already reversed and starts as None. curr heads the untouched part and starts at head. Each round saves nxt = curr.next, points curr.next at prev, moves prev to curr and moves curr to nxt. The save comes first because the flip overwrites the only link to the rest of the list. Each round moves one node from the untouched list to the front of the reversed list. When curr is None, prev is the new head. For positions left to right, I use a dummy node, walk before to the node before left, run the same rounds right - left + 1 times, and reconnect with before.next = prev and tail.next = curr. The time is O(N) and the space is O(1)."
Common Questions
- What is the time and space complexity?
O(N)time, because each node is flipped once.O(1)space, because the loop keeps onlyprev,currandnxt. A recursive solution is alsoO(N)time but usesO(N)space for the call stack.- Why do you need a
dummynode inreverse_between? The segment can start at the head. Then no real node is before it, and
before.next = prevwould have nothing to change.dummygives the head a node before it. The function returnsdummy.next, which is the new head in every case.- Why not copy the values into an array, reverse it and write the values back?
It works, but it uses
O(N)extra space. The statement of Reverse Linked List (LC 206) asks for the nodes to be rewired, and the follow-up asks for an iterative and a recursive version. Rewiring keeps the space atO(1).- How do you reverse a list in groups of k?
Count
knodes frombefore.next. If fewer thankremain, return. Otherwise run the flip loopktimes, reconnect withbefore.next = prevandtail.next = curr, and setbefore = tailfor the next group. This is Reverse Nodes in k-Group (LC 25).- How do you check that a linked list is a palindrome in
O(1)space? Find the middle, reverse the second half in place with the flip loop, and compare the two halves node by node. This is Palindrome Linked List (LC 234). If the list must stay unchanged, reverse the second half again after the comparison.
SWE Reasoning
Spot it
- The input is a singly linked list, and the statement says reverse it, or reverse part of it, or reverse groups of
knodes. - The extra space must be
O(1), so you cannot copy the values into an array and write them back. - The second half of a list must be compared or merged with the first half in reverse order (Palindrome Linked List (LC 234), Reorder List (LC 143)).
- The statement gives two positions and asks to reverse the nodes between them (Reverse Linked List II (LC 92)).
The invariant, step by step
- Before the loop,
previsNoneandcurrishead. The reversed list is empty. The untouched list is the whole list. nxt = curr.nextsaves the untouched list that followscurr.curr.next = prevmakescurrpoint at the reversed list, socurris now the head of a longer reversed list.prev = currnames that new head, andcurr = nxtmakes the saved list the untouched list.- Every node is in exactly one of the two lists after every round, and the untouched list is one node shorter.
- When
currisNone, the untouched list is empty.prevheads the whole reversed list, soreturn prev.
Traps
curr.next = prevbeforenxt = curr.next. The flip overwrites the only link to the rest of the list. For[1, 2, 3], the result is[1].return head. The old head is the tail after the loop. Returnprev.before = headinreverse_between. Whenleftis 1, the node before the segment isdummy. With[1, 2, 3, 4, 5],left = 1andright = 2, the result is[1, 3, 2, 4, 5]instead of[2, 1, 3, 4, 5].- Reading
tailafterbefore.next = prev.tailwould be node 4, the new head of the segment. Thentail.next = currpoints node 4 at node 5, and nodes 3 and 2 are cut out of the list. - Reversing a last group shorter than
k. In Reverse Nodes in k-Group (LC 25), countknodes first. If fewer remain, stop without flipping.
Practice
Builds on Dummy Node, which you haven’t finished yet.
In-Place Linked List Reversal (Reverse Linked List II, Reverse Nodes in k-Group)
You get head, the first node of a singly linked list. Each node holds a value val and a pointer next to the node after it; the last node's next is None, and an empty list has head = None.
Turn the list around: the node that was last must come first, and every node must point to the one that used to come before it. Return the first node of the reversed list (None for an empty list, written []).
Follow-up: once you have one version, write the other one too, a loop and a recursive function.
5, the old last node, is the new head and 1 ends the list.Linked List Reversal
head ➔ rewire each next pointer ➔ reversed list| 1 | from typing import Optional |
| 2 | |
| 3 | |
| 4 | class ListNode: |
| 5 | def __init__(self, val: int = 0, next: Optional["ListNode"] = None): |
| 6 | self.val = val |
| 7 | self.next = next |
| 8 | |
| 9 | |
| 10 | def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]: |
| 11 | """Reverse Linked List: flip every next pointer in one pass. |
| 12 | Time: O(N) | Space: O(1) |
| 13 | """ |
| 14 | prev = None # Head of the reversed part: empty at the start |
| 15 | curr = head # First node not flipped yet |
| 16 | while curr: |
| 17 | nxt = curr.next # Save the rest BEFORE the flip overwrites curr.next |
| 18 | curr.next = prev # Flip: curr now points back at the reversed part |
| 19 | prev = curr # The reversed part grows by one node |
| 20 | curr = nxt # Step into the saved rest |
| 21 | return prev # The old tail is the new head |
| 22 | |
| 23 | |
| 24 | def reverse_between(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: |
| 25 | """Reverse Linked List II: reverse positions left..right (1-indexed) in one pass. |
| 26 | Time: O(N) | Space: O(1) |
| 27 | """ |
| 28 | dummy = ListNode(0, head) # The segment may start at the head: give it a node before it |
| 29 | before = dummy |
| 30 | for _ in range(left - 1): # Walk to the node just before position left |
| 31 | before = before.next |
| 32 | prev = None |
| 33 | curr = before.next |
| 34 | for _ in range(right - left + 1): # The same flip, exactly right - left + 1 times |
| 35 | nxt = curr.next |
| 36 | curr.next = prev |
| 37 | prev = curr |
| 38 | curr = nxt |
| 39 | tail = before.next # The segment's old first node is now its last |
| 40 | before.next = prev # Reattach the reversed segment... |
| 41 | tail.next = curr # ...and hang the untouched rest behind it |
| 42 | return dummy.next |
prev heads the nodes already reversed and curr heads the nodes not touched yet: every node is in exactly one of the two lists.Reversing a singly linked list only needs every next pointer to point the other way, so walk the list once with two pointers: prev heads the part already reversed (it starts as None) and curr is the first node not flipped yet; each step points curr.next back at prev, then moves prev and curr one node forward. Each step moves exactly one node from the front of the untouched part to the front of the reversed part, so no node is lost or visited twice, and when curr falls off the end, prev is the new head. reverse_between runs the same steps right - left + 1 times from the node before position left, then reconnects both ends with before.next = prev and tail.next = curr. The trap is the order of the lines: curr.next = prev overwrites the only link to the rest of the list, so save nxt = curr.next first; flip first and every node after curr is lost.
See it run
Linked list reversal, head = [1, 2, 3, 4, 5]
prev Nonecurr 1
Each circle is a node and each arrow is its next link. The arrows change direction one node at a time.
prevthe head of the part that is already reversedcurrthe node whose link is flipped nownxtthe saved rest of the listnew linkthe link that was just flippedlostnodes that no variable and no link reaches any more
prev is None and curr is the head, node 1. Every link still points forward.
Gotcha 1 of 4
- The trap
Gotcha 1: Writing
curr.next = prevbefore savingnxtMistakewhile curr: curr.next = prev nxt = curr.nextFixwhile curr: nxt = curr.next curr.next = prevWhat happens:
curr.nextis the only link fromcurrto the rest of the list.curr.next = prevoverwrites that link. Thennxt = curr.nextsavesprev, which isNoneon the first step. The loop ends after one node, and every node aftercurris lost.Example: head = [1, 2, 3]Mistake: returns [1]Fix: returns [3, 2, 1]
- The data is an array you can index, as in Rotate Array (LC 189): reverse by swapping values from both ends of a range, not by rewiring
nextpointers. See Three-Reversals Algorithm
Deep Dive
Why every node moves from one list to the other
A singly linked list stores one pointer per node, next. Reversing the list means that every next points the other way. The old tail becomes the head, and the old head points at None.
The loop keeps two lists. prev is the head of the part that is already reversed. It starts as None, which is an empty list. curr is the head of the part that is not touched yet. It starts as head. Every node is in exactly one of the two lists.
One round does four things. nxt = curr.next saves the rest of the untouched part. curr.next = prev makes curr point at the reversed part. prev = curr makes curr the new head of the reversed part. curr = nxt steps into the saved rest. So one round moves exactly one node from the front of the untouched list to the front of the reversed list.
Trace head = [1, 2, 3, 4, 5] from Reverse Linked List (LC 206). After round 1, the reversed list is 1 and the untouched list is 2, 3, 4, 5. After round 2, the reversed list is 2, 1. After round 5, the reversed list is 5, 4, 3, 2, 1 and curr is None, so the loop stops. prev is the new head.
Each node is moved once, and each round does a fixed number of steps. So the loop takes N rounds. An empty list never enters the loop, and return prev returns None.
Why nxt must be saved before the flip
curr.next is the only link from curr to the rest of the list. The line curr.next = prev overwrites that link. After it, no variable and no pointer reaches the nodes behind curr.
Look at the trap step on the board. Suppose the code runs curr.next = prev first. For the head 1, prev is None, so node 1 now points at None. Then nxt = curr.next saves None, not node 2. The loop sets curr = None and stops after one round. The nodes 2, 3, 4, 5 still point at each other, but nothing points at node 2. They are lost, and the function returns a list with one node.
The correct order is: save, flip, move prev, move curr. The save must come first because it reads the link that the flip destroys.
A second mistake is return head. When the loop ends, the old head is the tail. Its next is None, so returning it gives a list with one node. The new head is prev.
Reversing only the positions from left to right
Reverse Linked List II (LC 92) reverses the nodes from position left to position right and keeps the others. reverse_between runs the same four lines, but only right - left + 1 times, and then it reconnects both ends.
Trace head = [1, 2, 3, 4, 5] with left = 2 and right = 4. dummy is a node placed before the head. before starts at dummy and moves left - 1 = 1 time, so before is node 1. prev is None and curr is node 2.
Three rounds flip node 2, node 3 and node 4. Now prev is node 4, the head of the reversed part. curr is node 5, the first node after the segment. Node 2 points at None.
tail = before.next reads node 2, the first node of the segment, which is now its last node. before.next = prev makes node 1 point at node 4. tail.next = curr makes node 2 point at node 5. The result is [1, 4, 3, 2, 5].
tail must be read before before.next = prev runs, because that line overwrites the only link to node 2. dummy is needed for left = 1. Then no real node is before the segment, and dummy.next is what the function returns.
Cost and the problems that reuse the flip
Both functions take O(N) time, because each node is visited a constant number of times. They take O(1) space: three pointers and, in reverse_between, dummy, before and tail. A recursive version needs O(N) space for the call stack.
Palindrome Linked List (LC 234) finds the middle, reverses the second half in place and compares the two halves node by node. Reorder List (LC 143) also reverses the second half, and then it takes one node from each half in turn.
Reverse Nodes in k-Group (LC 25) uses the reverse_between steps for each group of k nodes. A counting loop checks first that k nodes remain. A last group with fewer than k nodes stays as it is. Without that check, the flip loop would reverse the short group as well.
If you can index the data, as with an array, do not rewire anything. Swap values from both ends instead, as the Three-Reversals Algorithm card does.
60-Second Pitch
"I reverse the list in place with two pointers. prev heads the part that is already reversed and starts as None. curr heads the untouched part and starts at head. Each round saves nxt = curr.next, points curr.next at prev, moves prev to curr and moves curr to nxt. The save comes first because the flip overwrites the only link to the rest of the list. Each round moves one node from the untouched list to the front of the reversed list. When curr is None, prev is the new head. For positions left to right, I use a dummy node, walk before to the node before left, run the same rounds right - left + 1 times, and reconnect with before.next = prev and tail.next = curr. The time is O(N) and the space is O(1)."
Common Questions
- What is the time and space complexity?
O(N)time, because each node is flipped once.O(1)space, because the loop keeps onlyprev,currandnxt. A recursive solution is alsoO(N)time but usesO(N)space for the call stack.- Why do you need a
dummynode inreverse_between? The segment can start at the head. Then no real node is before it, and
before.next = prevwould have nothing to change.dummygives the head a node before it. The function returnsdummy.next, which is the new head in every case.- Why not copy the values into an array, reverse it and write the values back?
It works, but it uses
O(N)extra space. The statement of Reverse Linked List (LC 206) asks for the nodes to be rewired, and the follow-up asks for an iterative and a recursive version. Rewiring keeps the space atO(1).- How do you reverse a list in groups of k?
Count
knodes frombefore.next. If fewer thankremain, return. Otherwise run the flip loopktimes, reconnect withbefore.next = prevandtail.next = curr, and setbefore = tailfor the next group. This is Reverse Nodes in k-Group (LC 25).- How do you check that a linked list is a palindrome in
O(1)space? Find the middle, reverse the second half in place with the flip loop, and compare the two halves node by node. This is Palindrome Linked List (LC 234). If the list must stay unchanged, reverse the second half again after the comparison.
SWE Reasoning
Spot it
- The input is a singly linked list, and the statement says reverse it, or reverse part of it, or reverse groups of
knodes. - The extra space must be
O(1), so you cannot copy the values into an array and write them back. - The second half of a list must be compared or merged with the first half in reverse order (Palindrome Linked List (LC 234), Reorder List (LC 143)).
- The statement gives two positions and asks to reverse the nodes between them (Reverse Linked List II (LC 92)).
The invariant, step by step
- Before the loop,
previsNoneandcurrishead. The reversed list is empty. The untouched list is the whole list. nxt = curr.nextsaves the untouched list that followscurr.curr.next = prevmakescurrpoint at the reversed list, socurris now the head of a longer reversed list.prev = currnames that new head, andcurr = nxtmakes the saved list the untouched list.- Every node is in exactly one of the two lists after every round, and the untouched list is one node shorter.
- When
currisNone, the untouched list is empty.prevheads the whole reversed list, soreturn prev.
Traps
curr.next = prevbeforenxt = curr.next. The flip overwrites the only link to the rest of the list. For[1, 2, 3], the result is[1].return head. The old head is the tail after the loop. Returnprev.before = headinreverse_between. Whenleftis 1, the node before the segment isdummy. With[1, 2, 3, 4, 5],left = 1andright = 2, the result is[1, 3, 2, 4, 5]instead of[2, 1, 3, 4, 5].- Reading
tailafterbefore.next = prev.tailwould be node 4, the new head of the segment. Thentail.next = currpoints node 4 at node 5, and nodes 3 and 2 are cut out of the list. - Reversing a last group shorter than
k. In Reverse Nodes in k-Group (LC 25), countknodes first. If fewer remain, stop without flipping.