Reverse a Stretch

MediumLinked List

Problem

A train is a singly linked list of wagons numbered from 1. Maintenance needs the wagons from position left to position right (inclusive) in reverse order; every other wagon stays where it is.

Given the head, left and right, reverse that stretch in one pass and return the head.

Example 1

Input:
head = [1, 2, 3, 4, 5], left = 2, right = 4
Output:
[1, 4, 3, 2, 5]

Wagons 2..4 (values 2, 3, 4) are reversed.

Example 2

Input:
head = [6], left = 1, right = 1
Output:
[6]

Constraints

  • 1 ≤ number of nodes ≤ 500
  • -500 ≤ node.val ≤ 500
  • 1 ≤ left ≤ right ≤ number of nodes

Hint

Show the first hint

Reversing a whole list is easy; the trouble is reconnecting the reversed part to its neighbours.

Walkthrough

How to approach it

01Clarify before coding

  • Are positions 1-based? Yes.
  • Can left be 1 (the head moves)? Yes; a dummy node handles it.
  • Can left equal right? Yes: nothing changes.

02Brute force

Copy the values in the stretch to an array, reverse it and write the values back.

Cost: O(n) time and O(right - left) space; it also moves values instead of relinking nodes.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.