grid47 Exploring patterns and algorithms
Oct 28, 2024
6 min read
Solution to LeetCode 92: Reverse Linked List II Problem
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the linked list starting at position left and ending at position right. Return the modified linked list.
Problem
Approach
Steps
Complexity
Input: The function receives the head of a singly linked list and two integers `left` and `right` representing the positions in the list to reverse.
Example: Input: head = [7,9,11,5,2], left = 3, right = 5
Constraints:
• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n
Output: Return the head of the modified singly linked list after reversing the specified section.
Example: Output: [7,9,2,5,11]
Constraints:
• The output list retains all nodes from the original list.
• The reversed portion is accurately modified while the rest remains untouched.
Goal: Reverse the nodes of a singly linked list between positions `left` and `right` in a single traversal.
Steps:
• Create a dummy node pointing to the head of the list.
• Traverse to the node immediately before position `left`.
• Perform in-place node re-linking to reverse the sublist between `left` and `right`.
• Reconnect the reversed sublist to the remaining parts of the list.
Goal: Ensure proper handling of edge cases and valid inputs.
Steps:
• Handle lists with a single node or where `left == right`.
• Ensure the function operates within O(1) space complexity apart from the input list.
Assumptions:
• The input list is non-circular and contains valid node values.
• `left` and `right` are always within valid bounds.
• Input: Input: head = [3,6,1,8,5], left = 2, right = 4
• Explanation: Reverse the sublist from position 2 to 4. Resulting list is [3,8,1,6,5].
• Input: Input: head = [10], left = 1, right = 1
• Explanation: Since the list contains a single node and `left == right`, the list remains [10].
Approach: Reverse a sublist in the linked list using in-place re-linking. Maintain pointers to manage the reversed sublist and the unaffected portions efficiently.
Observations:
• Reversing a sublist can be done by adjusting the next pointers of the nodes within the range.
• A dummy node helps handle edge cases cleanly, such as reversing from the head of the list.
• Minimize traversal by reversing the sublist in-place.
• Optimize space usage to O(1) by not using additional data structures.
Steps:
• Initialize a dummy node pointing to the head of the list.
• Use a pointer to traverse to the node just before the reversal starts.
• Iteratively reverse the next pointers of nodes in the specified range.
• Reconnect the reversed sublist to the preceding and succeeding parts of the list.
Empty Inputs:
• Input list is NULL.
Large Inputs:
• List has 500 nodes and requires reversing a large sublist.
Special Values:
• Input values at the boundary of valid ranges, e.g., `left = 1`, `right = n`.
Constraints:
• Ensure nodes outside the reversal range remain unmodified.
ListNode*reverseBetween(ListNode* head, int left, int right) {
if (!head) return head;
ListNode* dummy =new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;
for (int i =0; i < left -1; ++i) {
prev = prev->next;
}
ListNode* curr = prev->next;
ListNode* next = curr->next;
for (int i =0; i < right - left; ++i) {
curr->next = next->next;
next->next = prev->next;
prev->next = next;
next = curr->next;
}
return dummy->next;
}
1 : Function Declaration
ListNode*reverseBetween(ListNode* head, int left, int right) {
Declares a function `reverseBetween` that takes a linked list `head`, a starting position `left`, and an ending position `right` as input and returns the modified linked list.
2 : Edge Case Check
if (!head) return head;
Checks if the input linked list is empty. If so, returns the head directly.
3 : Dummy Node Initialization
ListNode* dummy =new ListNode(0);
Creates a dummy node to simplify the reversal process, especially when reversing from the beginning of the list.
4 : Pointer Assignment
dummy->next = head;
Sets the `next` pointer of the dummy node to the head of the original linked list.
5 : Pointer Initialization
ListNode* prev = dummy;
Initializes a `prev` pointer to the dummy node, which will be used to track the node before the reversal range.
6 : Loop Iteration, Pointer Update
for (int i =0; i < left -1; ++i) {
prev = prev->next;
}
Iterates `left - 1` times to move the `prev` pointer to the node just before the start of the reversal range.
7 : Pointer Initialization
ListNode* curr = prev->next;
Initializes a `curr` pointer to the first node in the reversal range.
8 : Pointer Initialization
ListNode* next = curr->next;
Initializes a `next` pointer to the node after `curr`, which will be used to temporarily store the next node during the reversal process.
9 : Loop Iteration, Pointer Manipulation
for (int i =0; i < right - left; ++i) {
Iterates `right - left` times to reverse the nodes in the specified range.
10 : Pointer Manipulation
curr->next = next->next;
Sets the `next` pointer of the current node `curr` to the node after the next node.
11 : Pointer Manipulation
next->next = prev->next;
Sets the `next` pointer of the next node `next` to the node that `prev` currently points to, effectively reversing the link.
12 : Pointer Manipulation
prev->next = next;
Sets the `next` pointer of the `prev` node to the current `next` node, linking it to the reversed portion.
13 : Pointer Update
next = curr->next;
Moves the `next` pointer to the next node to be reversed in the next iteration.
14 : Return
return dummy->next;
Returns the head of the modified linked list, which is the `next` pointer of the dummy node.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The entire list may need to be traversed in the worst case, where `right = n`.
Best Case: O(1)
Worst Case: O(1)
Description: The solution uses constant space for pointers and variables.
