Hey Guys! Today we are going to daily leetcode problem. Let's get started with it!.
The problem at hand involves reversing a sublist within a singly linked list between specified positions. To briefly understand this, please be acquainted with how to reverse a linked list or the core concept behind it.
Problem: 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.
Understanding the Approach(Intuition)
Before diving into the code, let's understand the intuition behind the approach used in the provided C++ code.
We create a
dummy
node at the beginning of the list to handle the case where the sublist starts from the first node. This simplifies the code.We initialize a
prev
pointer to point to the node just before theleft
-th node. We iterate untilprev
reaches the node beforeleft
.We maintain a
curr
pointer to keep track of the current node which will be moved to the position right afterprev
.We then reverse the sublist from
left
toright
by iteratively moving nodes betweenleft
andright
. This is achieved by adjusting thenext
pointers of the nodes.Finally, we return the modified list with the sublist reversed.
Example Walkthrough
Let's perform a step-by-step walkthrough of the code with an example linked list: 1 -> 2 -> 3 -> 4 -> 5
, and left = 2
and right = 4
.
Initially, a
dummy
node is created, andprev
is set todummy
. The list is:dummy -> 1 -> 2 -> 3 -> 4 -> 5
.The
prev
pointer is moved to the node beforeleft
, which is1
. Thecurr
pointer is set to2
. The list remains the same.-
We enter the loop to reverse the sublist.
-
nextNode
is set to3
. -
curr->next
points tonextNode->next
, making2
point to4
. -
nextNode->next
is updated toprev->next
, making3
point to2
. -
prev->next
is updated tonextNode
, making1
point to3
.
-
The list becomes: dummy -> 1 -> 3 -> 2 -> 4 -> 5
.
The loop continues, and the same steps are repeated to reverse the remaining part of the sublist.
Finally, the modified list is returned without the
dummy
node.
The Code
Here's the code to reverse a sublist in a linked list:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (head == nullptr || left == right) {
return head;
}
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;
// Move prev to the node before the left-th node
for (int i = 1; i < left; ++i) {
prev = prev->next;
}
ListNode* curr = prev->next;
// Reverse the sublist from left to right
for (int i = left; i < right; ++i) {
ListNode* nextNode = curr->next;
curr->next = nextNode->next;
nextNode->next = prev->next;
prev->next = nextNode;
}
return dummy->next;
}
Complexity Analysis:
Time Complexity: The algorithm makes a single pass through the list, so the time complexity is O(N), where N is the number of nodes in the list.
Space Complexity: The algorithm uses a constant amount of extra space, so the space complexity is O(1).
Top comments (0)