Medium

Reverse Linked List II

LAB

Given a linked list encoded as an array, reverse the nodes from 1-indexed position left through right and return the resulting values.

EXAMPLES

Example 1

Input
{
  "head": [
    1,
    2,
    3,
    4,
    5
  ],
  "left": 2,
  "right": 4
}

Output
[
  1,
  4,
  3,
  2,
  5
]

FUNCTION SHAPE

head: intArrayleft: intright: int→intArray

SOLUTION NOTE

This "in-place partial reversal" technique is elegant because it avoids creating any new nodes and requires only one pass through the list.

Walk through the first example and this will be clear. Basically we just walk up to before we reverse the list. The 4 important nodes are: the node immediately before reversal, (index left -1) the first node being reversed (index left), the last node being reversed (index right), and the node immediately after reversal. (index right+1) We need to store these, reverse the list, and then re-wire accordingly at the end of the reversal.

pythonEXAMPLE

prev_node_before_reverse.next = last_node_reversed
first_node_reversed.next = first_node_after_reverse

Reveal reference solution +

pythonREFERENCE

def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    dummy = ListNode(-1, head)  # NEED THE DUMMY!!! WHAT IF WE REVERSE THE ENTIRE LIST!!!

    prev, curr = dummy, head
    for _ in range(left - 1):
        curr, prev = curr.next, curr

    prev_node_before_reverse = prev  # 1
    first_node_reversed = curr  # 2

    for _ in range(right - left + 1):
        curr.next, curr, prev = prev, curr.next, curr

    first_node_after_reverse = curr  # 5
    last_node_reversed = prev  # 4

    prev_node_before_reverse.next = last_node_reversed
    first_node_reversed.next = first_node_after_reverse

    return dummy.next

TimeO(n)

SpaceO(1)

Open on LeetCode ↗