Problem Description

Given the head of a singly linked list and two integers left and right (with 1-based indexing), reverse the nodes of the list from position left to position right, and return the modified list's head. The reversal should be done in-place and only the nodes between left and right (inclusive) are affected. All other nodes must remain in their original order and should not be recreated or reused. Only one valid solution is required, and you may not reuse or create new nodes for the reversed portion.

• Input: head (the head of a singly linked list), left (integer), right (integer)
• Output: The head of the modified linked list after reversing the specified sublist
• Constraints: 1 ≤ left ≤ right ≤ length of list
• Do not allocate new nodes for the reversed section; reverse in-place

Thought Process

The problem asks us to reverse a segment of a singly linked list, specifically from position left to right. At first glance, one might consider extracting the sublist, reversing it, and then reconnecting it. However, since the reversal must be done in-place and without creating new nodes, we need to manipulate the pointers directly.

The brute-force approach would be to traverse the list, copy the values of the segment into an array, reverse the array, and write them back. However, this would violate the in-place constraint and waste space.

Instead, by carefully keeping track of the nodes before, within, and after the segment to reverse, we can perform the reversal efficiently by re-pointing the next pointers. This requires careful pointer manipulation but is optimal in both time and space.

Solution Approach

We will reverse the sublist in-place by manipulating pointers. Here’s a step-by-step plan:

1. Add a dummy node: To handle cases where left = 1, we introduce a dummy node before the head. This simplifies pointer management at the head.
2. Traverse to the node before left: Let’s call this node prev. This node will connect to the reversed segment's head after reversal.
3. Reverse the sublist: Starting from left, we iteratively reverse the next pointers for right - left + 1 nodes.
4. Reconnect the reversed sublist: After the reversal, connect prev.next to the new head of the reversed segment, and the tail of the reversed segment to the node after right.
5. Return the new head: The list's head may have changed, so we return dummy.next.

This approach ensures all pointer changes are performed in-place, and only the specified segment is reversed.

Example Walkthrough

Let’s walk through an example:

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

1. Add a dummy node: dummy → 1 → 2 → 3 → 4 → 5
2. Move prev to node 1 (the node before position 2).
3. Reverse the segment 2-4:
   • First iteration: curr = 2, detach 3 and insert after prev → dummy → 1 → 3 → 2 → 4 → 5
   • Second iteration: curr = 2, detach 4 and insert after prev → dummy → 1 → 4 → 3 → 2 → 5
4. The list is now: 1 → 4 → 3 → 2 → 5
5. Return dummy.next as the new head.

The sublist from position 2 to 4 has been reversed, and all other nodes remain in order.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        if not head or left == right:
            return head

        dummy = ListNode(0)
        dummy.next = head
        prev = dummy

        # Move prev to the node before 'left'
        for _ in range(left - 1):
            prev = prev.next

        # Start reversing
        curr = prev.next
        for _ in range(right - left):
            temp = curr.next
            curr.next = temp.next
            temp.next = prev.next
            prev.next = temp

        return dummy.next
      

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (!head || left == right) return head;

        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;

        // Move prev to the node before 'left'
        for (int i = 0; i < left - 1; ++i) {
            prev = prev->next;
        }

        ListNode* curr = prev->next;
        for (int i = 0; i < right - left; ++i) {
            ListNode* temp = curr->next;
            curr->next = temp->next;
            temp->next = prev->next;
            prev->next = temp;
        }
        return dummy.next;
    }
};
      

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left == right) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

        // Move prev to the node before 'left'
        for (int i = 0; i < left - 1; ++i) {
            prev = prev.next;
        }

        ListNode curr = prev.next;
        for (int i = 0; i < right - left; ++i) {
            ListNode temp = curr.next;
            curr.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
        return dummy.next;
    }
}
      

/**
 * Definition for singly-linked list.
 * 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) {
    if (!head || left === right) return head;

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

    // Move prev to the node before 'left'
    for (let i = 0; i < left - 1; ++i) {
        prev = prev.next;
    }

    let curr = prev.next;
    for (let i = 0; i < right - left; ++i) {
        let temp = curr.next;
        curr.next = temp.next;
        temp.next = prev.next;
        prev.next = temp;
    }
    return dummy.next;
};
      

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(N), as you need to traverse the list at least once.
  • Space Complexity: O(N), due to copying node values into an array for reversal.
• Optimized in-place approach (above):
  • Time Complexity: O(N), since we traverse the list at most twice (once to reach left, and once to reverse up to right).
  • Space Complexity: O(1), as all operations are done in-place without allocating new nodes or data structures.

The optimized solution is both time and space efficient, making it suitable for large lists.

Summary

To reverse a sublist of a singly linked list between two given positions, we use a dummy node to simplify pointer manipulation, locate the node before the reversal segment, and perform in-place pointer reversal for the specified range. This method is efficient, elegant, and adheres to the problem's constraints of in-place reversal and no node reuse. The key insight is to manipulate pointers directly, avoiding unnecessary space usage and achieving O(N) time and O(1) space complexity.