Reverse only a section
Reverse the nodes between two places by repeatedly pulling the next node to the front of the section, leaving the rest of the list untouched. About 16 minutes.
Pull each node to the front
Reversing the whole list used a previous and a current pointer. For a section, there is a neat variation. Stand on the node just before the section. The first node of the section, called cur, stays where it is.
Each round, take the node right after cur and move it to just after the standing node. It becomes the new front of the section. After enough rounds, the section is reversed, and cur has drifted to its back.
prev = dummy
for _ in range(left - 1):
prev = prev.next # stand before it- cur
- 4
- stand
- 9
Stand on box 9, just before the section. Box 4 is cur and stays put.
Count rounds, add a dummy
A section of length m needs m minus 1 rounds, which is right minus left rounds. First walk left minus 1 times from a dummy node to reach the standing place.
The dummy is a node placed in front of the head. If the section begins at place 1, the standing node is the dummy itself, and the same code works with no special case. Return the dummy's next at the end.
dummy = ListNode(0, head) ... return dummy.next
Reversing places 3 to 7 of a list. How many rounds of pulling a node to the front?
- A4
- B5
- C3
Show the answer
4. The section has 5 nodes, and each round moves one of the 4 nodes behind the first.
Reverse part of a list
Given the head of a singly linked list and two places left and right (counting from 1, with left at most right), reverse the nodes from place left to place right and return the head. Nodes outside that section stay in their places.
head = [1, 2, 3, 4, 5], left = 2, right = 4 → [1, 4, 3, 2, 5]
1 ≤ number of nodes ≤ 5,000 · 1 ≤ left ≤ right ≤ number of nodes