Reverse a Linked List, Then Reverse a Sublist In Place
Problem statement
This is a two-step question on a singly linked list.
- Write
reverse_list(head), which reverses the whole list and returns the new head. - Then write
reverse_between(head, left, right), which reverses only the nodes at positionsleftthroughright(1-based, inclusive), leaves every other node where it is, and returns the head of the list. The head changes whenleft == 1.
Both must work in place: relink the existing nodes, use $O(1)$ extra space, and do not create new nodes.
class ListNode:
def __init__(self, val=0, next=None): ...
def reverse_list(head: ListNode) -> ListNode: ...
def reverse_between(head: ListNode, left: int, right: int) -> ListNode: ...
The judge calls a wrapper in the editor that builds two fresh lists from an array of values, calls each function once and returns both results as arrays [reversed_whole, reversed_between]. The wrapper rejects any result that contains a newly allocated node.
Constraints
- $1 \le n \le 500$ nodes, $-500 \le$ node value $\le 500$
- $1 \le$
left$\le$right$\le n$
Examples
Example 1: values [1, 2, 3, 4, 5], left = 2, right = 4 returns [[5, 4, 3, 2, 1], [1, 4, 3, 2, 5]].
Example 2: values [3, 5], left = 1, right = 2 returns [[5, 3], [5, 3]] (the sublist is the whole list, so the head changes).
Example 3: values [7], left = 1, right = 1 returns [[7], [7]].
Show hint
When you redirect a node's next pointer, what must you hold on to first so the rest of the list is not lost?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.