Reverse Linked List II

Medium Linked List Front Middle Back Pointer Original on LeetCode

Reverse Linked List II is a medium linked list problem solved with the front middle back pointer pattern. The best approach, optimal (front insertion, one pass), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from collect values and write back up.

Problem

Reverse the nodes of a linked list from position left to position right (1-indexed, inclusive) and return the head. Nodes outside that range stay where they are.

Examples

Example 1

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

Example 2

Input
head = [7, 8], left = 1, right = 2
Output
[8, 7]

Constraints

  • 1 <= left <= right <= n <= 500
  • Follow-up: one pass.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Collect values and write backO(n)O(n)
Optimal (front insertion, one pass)O(n)O(1)

1Collect values and write back

TimeO(n)
SpaceO(n)

Copy the values in positions left..right into a list, then write them back in reverse.

  1. Walk to position left, collect right - left + 1 values.
  2. Walk again and overwrite them in reverse order.
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        List<Integer> vals = new ArrayList<>();
        ListNode p = head;
        for (int i = 1; i < left; i++) p = p.next;
        ListNode start = p;
        for (int i = left; i <= right; i++) { vals.add(p.val); p = p.next; }
        p = start;
        for (int i = vals.size() - 1; i >= 0; i--) { p.val = vals.get(i); p = p.next; }
        return head;
    }
}

2Optimal (front insertion, one pass)

TimeO(n)
SpaceO(1)

prev is the node before position left and cur is the first node of the sublist. Take the node after cur and move it right after prev, right - left times. cur slides toward the end and the sublist comes out reversed.

  1. Dummy node; move prev left - 1 steps; cur = prev.next.
  2. Repeat right - left times: move = cur.next; cur.next = move.next; move.next = prev.next; prev.next = move.
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0, head), prev = dummy;
        for (int i = 1; i < left; i++) prev = prev.next;
        ListNode cur = prev.next;
        for (int i = 0; i < right - left; i++) {
            ListNode move = cur.next;
            cur.next = move.next;
            move.next = prev.next;
            prev.next = move;
        }
        return dummy.next;
    }
}

Edge cases to test

  • left = 1 (the head changes)
  • left == right (nothing changes)

Hints

Hint 1

Stop at the node before position left. Then repeatedly move the node after the current one to the front of the sublist.

FAQ

What is the best time complexity for Reverse Linked List II?

Optimal (front insertion, one pass) runs in O(n) time and O(1) extra space.

Which pattern does Reverse Linked List II use?

It is a linked list problem that uses the front middle back pointer pattern. Other problems with the same pattern: Reverse Linked List, Reverse Nodes in k-Group, Palindrome Linked List.

Is there a brute force solution for Reverse Linked List II?

Yes. Collect values and write back takes O(n) time and O(n) space. Copy the values in positions left..right into a list, then write them back in reverse.

Which edge cases should I test for Reverse Linked List II?

left = 1 (the head changes); left == right (nothing changes).