Problem 205180 · medium · Phase 02 Linear Data Structures

Reverse a Middle Segment

linked list · reversal · pointer manipulation

Given the head of a singly linked list and two 1-based positions left and right with left <= right, reverse the nodes from position left to position right inclusive and return the head.

Examples

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, left = 2, right = 4
Output: 1 -> 4 -> 3 -> 2 -> 5

Input:  head = 5, left = 1, right = 1
Output: 5

Constraints

  • 1 <= number of nodes <= 10**4
  • 1 <= left <= right <= number of nodes
  • Target: O(n) time, O(1) extra space, one pass

Goals

  • Reverse a sub-range of nodes in place
  • Reconnect both ends of the reversed segment correctly
Starting Python…