Reverse Linked List II
Problem Description
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.
Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]
Constraints:
- The number of nodes in the list is
n. 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
Follow up: Could you do it in one pass?
Solve it on LeetCode
Approaches
1. Iterative Reversal with Extra Space
Intuition:
This approach leverages an extra data structure to reverse the segment of the linked list. We first traverse the list to the position where the reversal starts, collect nodes in an array for the part to be reversed, reverse the array, and finally rebuild the linked list using this array.
Steps:
- Traverse the list to find the part of the list that needs to be reversed.
- Store nodes to be reversed into an array.
- Reverse the array contents.
- Reconnect the nodes before, within, and after the reversed segment accordingly.
Code:
- Time Complexity: O(n), where n is the number of nodes in the list since we traverse the list a constant number of times.
- Space Complexity: O(n), due to the stack used for storing nodes to be reversed.
2. Iterative In-Place Reversal
Intuition:
Instead of using extra space, this approach manages all operations directly within the list structure. The key is to carefully manage pointers to reverse the sublist in place by detaching and reattaching nodes.
Steps:
- Traverse the linked list to the starting position of reversal.
- Reverse the sublist by changing pointers in place.
- Reconnect the reversed section to the remainder of the list.
Code:
- Time Complexity: O(n), where n is the number of nodes in the list, as we make a linear pass through the list.
- Space Complexity: O(1), no additional space is used; reversal is done in place.