92. Reverse Linked List II

Time: O(n)

Space: O(1)

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?