Reverse Linked List II

Medium
2007.

Reverse Linked List II

Reverse Linked List II is a medium coding problem on two pointers, asked in Amazon, Microsoft, Meta and Apple interviews.

Given the head of a singly linked list and two integers left <= right, reverse the nodes from position left to position right (positions counted from 1), leaving the rest of the list as it is. Return the head of the list.

Example 1

Input
head = [1,2,3,4,5], left = 2, right = 4
Output
[1,4,3,2,5]
Explanation
The segment 2 → 3 → 4 becomes 4 → 3 → 2.

Example 2

Input
head = [5], left = 1, right = 1
Output
[5]

Example 3

Input
head = [3,5,8], left = 1, right = 3
Output
[8,5,3]
Explanation
The range can cover the whole list, head included.

Constraints

  • The number of nodes in the list is n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

Follow-up: Could you do it in one pass?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function(head, left, right) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Reverse Linked List II — Solution in Python, Java & C++

Reverse Linked List II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on two pointers.

Reverse Linked List II is a medium coding problem on two pointers, asked in Amazon, Microsoft, Meta and Apple interviews.

  • Difficulty: Medium
  • Topics: Two Pointers
  • Asked at: Amazon, Microsoft, Meta, Apple
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the head of a singly linked list and two integers left <= right, reverse the nodes from position left to position right (positions counted from 1), leaving the rest of the list as it is. Return the head of the list.

Example 1

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Explanation: The segment 2 → 3 → 4 becomes 4 → 3 → 2.

Example 2

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

Example 3

Input: head = [3,5,8], left = 1, right = 3
Output: [8,5,3]
Explanation: The range can cover the whole list, head included.

Constraints

  • The number of nodes in the list is n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

Follow-up: Could you do it in one pass?

Hints for Reverse Linked List II

  1. Hint 1

    Find the node just before position left; everything before it stays put.

  2. Hint 2

    Reverse the segment by repeatedly taking the node right after the segment's (moving) first node and moving it to the front of the segment.

  3. Hint 3

    That front insertion is three link changes per node, done right - left times. A dummy node in front of the head covers left = 1.

How to solve Reverse Linked List II

Stand on the node before the segment (pre). The segment's first node cur will end up last; one by one, pull the node after cur out and insert it right after pre. After right - left moves the segment is reversed, in a single pass.

Approach

  1. Create a dummy node before head; walk pre forward left - 1 steps from the dummy.
  2. Let cur = pre.next (the first node of the segment).
  3. Repeat right - left times: nxt = cur.next; cur.next = nxt.next; nxt.next = pre.next; pre.next = nxt.
  4. Return dummy.next.

Why it works

Each move takes the next unreversed node of the segment and places it at the segment's front, so after i moves the first i + 1 nodes of the segment appear in reverse order directly after pre, with cur linked to the rest. After right - left moves the whole segment is reversed and still attached on both sides.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • When left = 1 the head changes — return dummy.next, not the original head.
  • cur never moves: it is always the segment's last node, and its next keeps the tail attached.
  • left == right needs no work; the loop runs zero times.

Reference solution

Python

from typing import Optional

def reverseBetween(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    pre = dummy
    for _ in range(left - 1):
        pre = pre.next
    cur = pre.next
    for _ in range(right - left):
        nxt = cur.next
        cur.next = nxt.next
        nxt.next = pre.next
        pre.next = nxt
    return dummy.next

Java

public static ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(0, head), pre = dummy;
    for (int i = 1; i < left; i++) pre = pre.next;
    ListNode cur = pre.next;
    for (int j = 0; j < right - left; j++) {
        ListNode nxt = cur.next;
        cur.next = nxt.next;
        nxt.next = pre.next;
        pre.next = nxt;
    }
    return dummy.next;
}

C++

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(0, head);
    ListNode* pre = &dummy;
    for (int i = 1; i < left; i++) pre = pre->next;
    ListNode* cur = pre->next;
    for (int j = 0; j < right - left; j++) {
        ListNode* nxt = cur->next;
        cur->next = nxt->next;
        nxt->next = pre->next;
        pre->next = nxt;
    }
    return dummy.next;
}

JavaScript

var reverseBetween = function(head, left, right) {
    var dummy = new ListNode(0, head), pre = dummy;
    for (var i = 1; i < left; i++) pre = pre.next;
    var cur = pre.next;
    for (var j = 0; j < right - left; j++) {
        var nxt = cur.next;
        cur.next = nxt.next;
        nxt.next = pre.next;
        pre.next = nxt;
    }
    return dummy.next;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 165 two pointers problems · the whole catalogue

Learn the technique: Two Pointers Technique