Linked List - Reverse Linked List II

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. Positions are 1-indexed.

Input: head = [1, 2, 3, 4, 5], left = 2, right = 4
Output: [1, 4, 3, 2, 5]
Explanation: The sublist from position 2 to 4 ([2, 3, 4]) is reversed to [4, 3, 2].

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

We use a single-pass approach. A dummy node is prepended to handle edge cases where reversal starts from the head. We advance to the node just before position left (called prev), then reverse the sublist in-place using an insertion technique.

Create a dummy node that points to head. Set prev = dummy.
Advance prev exactly left - 1 steps so it sits just before the sublist start.
Let curr = prev.next (the first node of the sublist to reverse).
Repeat right - left times: take the node after curr, remove it from its position, and insert it immediately after prev. This effectively reverses the sublist one node at a time.
Return dummy.next as the new head.

class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } public class ReverseLinkedListII { public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; // Move prev to (left-1)-th node for (int i = 0; i < left - 1; i++) { prev = prev.next; } ListNode curr = prev.next; // Perform (right - left) insertions for (int i = 0; i < right - left; i++) { ListNode next = curr.next; curr.next = next.next; next.next = prev.next; prev.next = next; } return dummy.next; } }

Complexity Analysis:

Time complexity: O(n) where n is the length of the linked list. We traverse the list at most once.
Space complexity: O(1) since we reverse in-place using only a constant number of pointers.