Reverse a Linked List, Then Reverse a Sublist In Place

Reported in interviews at Ericsson Microsoft

Problem statement

This is a two-step question on a singly linked list.

  1. Write reverse_list(head), which reverses the whole list and returns the new head.
  2. Then write reverse_between(head, left, right), which reverses only the nodes at positions left through right (1-based, inclusive), leaves every other node where it is, and returns the head of the list. The head changes when left == 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.

Related free problems