Reverse Linked List II

medium linked list pointers

Problem

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Input1→2→3→4→5, left=2, right=4

Output1→4→3→2→5

Only the middle three nodes flip.

list (comma-separated)

left (1-indexed)

right

def reverse_between(head, left, right):
    dummy = ListNode(0, head)
    prev = dummy
    for _ in range(left - 1):
        prev = prev.next
    cur = prev.next
    for _ in range(right - left):
        moved = cur.next
        cur.next = moved.next
        moved.next = prev.next
        prev.next = moved
    return dummy.next

function reverseBetween(head, left, right) {
  const dummy = { val: 0, next: head };
  let prev = dummy;
  for (let i = 1; i < left; i++) prev = prev.next;
  const cur = prev.next;
  for (let i = 0; i < right - left; i++) {
    const moved = cur.next;
    cur.next = moved.next;
    moved.next = prev.next;
    prev.next = moved;
  }
  return dummy.next;
}

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 moved = cur.next;
            cur.next = moved.next;
            moved.next = prev.next;
            prev.next = moved;
        }
        return dummy.next;
    }
}

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(0, head);
    ListNode* 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* moved = cur->next;
        cur->next = moved->next;
        moved->next = prev->next;
        prev->next = moved;
    }
    return dummy.next;
}

Explanation

We only need to flip a middle chunk of the list, from position left to right, and leave the rest alone. The slick way is the head-insertion trick: repeatedly pull the node after our current one to the front of the segment.

A dummy head lets us reverse even when left is 1. We first walk prev to the node just before position left. Then cur is the first node of the segment and stays fixed; everything that follows gets yanked in front of it.

Each iteration takes moved = cur.next, unlinks it (cur.next = moved.next), and re-inserts it right after prev (moved.next = prev.next; prev.next = moved). Doing this right - left times reverses exactly the chosen window while the connections to the outside stay intact.

Example: 1→2→3→4→5 with left=2, right=4. The window 2,3,4 flips by pulling 3 then 4 ahead of 2, giving 1→4→3→2→5.

It is one pass over the segment with constant extra space, since we only re-point existing links.

Time: O(n) Space: O(1)