92. Reverse Linked List II

MediumView on LeetCode

Linked List

Time: O(n)

Space: O(1)

Problem Overview

Reverse only the sublist from position left to right.

Intuition

Reverse only the sublist from position left to right. Navigate to the node just before position left, then perform exactly (right-left) pointer reversals on the sublist, reconnecting the reversed portion back into the original list.

Algorithm

1Use a dummy node before head. Advance prev to the node at position left-1.
2cur = prev.next (start of sublist). For right-left iterations: remove cur.next and insert it right after prev.
3Return dummy.next.

Example Walkthrough

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

1.prev = node1. cur = node2.
2.Iteration 1: move node3 after node1. List: 1->3->2->4->5.
3.Iteration 2: move node4 after node1. List: 1->4->3->2->5.

Output: [1,4,3,2,5]

Common Pitfalls

•The "insert after prev" technique (not a full reversal loop) makes reconnection trivial - prev.next always points to the new head of the reversed section.

92.cs

// Approach: Single pass with a dummy node to simplify head manipulation.
// Walk forward to reach the node just before position 'left' (call it prev).
// Then perform (right - left) reversals: for each step, detach the node right after prev
// and insert it immediately after the dummy node's eventual predecessor (prev).
// This inserts nodes at the front of the reversed segment one by one.
// The dummy node avoids special-casing when the reversal starts at the head.
// Time: O(n) Space: O(1)

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class Solution
{
    public ListNode ReverseBetween(ListNode head, int left, int right)
    {
        if (head == null || left == right)
            return head;

        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;

        for (int i = 0; i < left - 1; ++i)
            prev = prev.next; // Point to the node before the sublist [m, n].

        ListNode tail = prev.next; // Be the tail of the sublist [m, n].

        // Reverse the sublist [m, n] one by one.
        for (int i = 0; i < right - left; ++i)
        {
            ListNode cache = tail.next;
            tail.next = cache.next;
            cache.next = prev.next;
            prev.next = cache;
        }

        return dummy.next;
    }
}

Was this solution helpful?