Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the portion of the linked list from position left to position right. The positions are 1-indexed. After reversing, the linked list should maintain its original structure around the reversed segment.

Problem Description

Your task is to reverse a specific sub-list within a larger linked list. You will be given the head of the linked list and two integers, left and right, indicating the start and end positions (inclusive) of the sub-list to be reversed. Positions are 1-indexed.

Key Requirements:

• Reverse the nodes of the linked list in-place from the left-th node to the right-th node.
• The links before the left-th node and after the right-th node should remain connected to the reversed sub-list correctly.
• The reversal should be done without creating new nodes.

Expected Behavior:

The function should return the head of the modified linked list.

Edge Cases to Consider:

• Reversing the entire list.
• Reversing a sub-list starting from the first node (left = 1).
• Reversing a sub-list ending at the last node.
• Reversing a single node (left = right).
• An empty linked list (though constraints will likely prevent this).

Examples

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Explanation: The sub-list [2,3,4] is reversed to [4,3,2]. The rest of the list remains unchanged.

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]
Explanation: Reversing a single node has no effect.

Example 3:

Input: head = [1,2,3,4,5], left = 1, right = 5
Output: [5,4,3,2,1]
Explanation: The entire list is reversed.

Constraints

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Notes

This problem is a variation of linked list reversal. Focus on identifying the nodes that will be the new head and tail of the reversed sub-list, and the nodes that will connect to these new ends. You'll likely need to keep track of several pointers: the node just before the reversal starts, the current node being processed during reversal, the previous node in the reversed portion, and the node immediately after the reversal ends.