Problem statement
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.
Problem statement taken from: https://leetcode.com/problems/reverselinkedlistii
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 <= 500
 1 <= left <= right <= n
Explanation
Iterative solution
The problem is similar to reverse a linked list but instead of a whole list we need to reverse
only a subset of this.
Let's say we consider a sublist 3 > 4 > 5 of the original list 1 > 2 > 3 > 4 > 5 > 6 > 7
which we want to reverse. The sublist needs to be reversed as 3 < 4 < 5.
Lets point our current node to 4 and previous node to 3.
We can easily reverse the current next pointer to previous by setting
current>next = previous
But in this case we won't be able to navigate to node 5. Hence we need one more pointer
let's call that as iterator that will help continue the link reversal process.
So we need to do the following:
iterator = current>next
current>next = prev
prev = current
current = iterator
We continue doing the above steps till we reach the right node.
Let's check the algorithm now.
 return NUll if head == NULL
 return head if left == right
 set current = head, prev = NULL
 loop while left > 1
 set prev = current
 update current = current>next
 decrement left
 decrement right
 set tailPrev = prev, tail = current, iterator = NULL
 loop while right > 0
 iterator = current>next
 current>next = prev
 prev = current
 current = iterator
 decrement right
 if tailPrev != NULL
 set tailPrev>next = prev
 else
 head = prev
 set tail>next = current
 return head
Let's check out our solutions in C++, Golang, and Javascript.
C++ solution
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if(head == NULL) {
return NULL;
}
if(left == right) {
return head;
}
ListNode *current = head, *prev = NULL;
while(left > 1) {
prev = current;
current = current>next;
left;
right;
}
ListNode *tailPrev = prev, *tail = current, *iterator = NULL;
while(right > 0) {
iterator = current>next;
current>next = prev;
prev = current;
current = iterator;
right;
}
if(tailPrev != NULL) {
tailPrev>next = prev;
} else {
head = prev;
}
tail>next = current;
return head;
}
};
Golang solution
func reverseBetween(head *ListNode, left int, right int) *ListNode {
if head == nil {
return nil
}
if left == right {
return head
}
current := head
var prev *ListNode
for left > 1 {
prev = current
current = current.Next
left
right
}
tailPrev, tail := prev, current
var iterator *ListNode
for right > 0 {
iterator = current.Next
current.Next = prev
prev = current
current = iterator
right
}
if tailPrev != nil {
tailPrev.Next = prev
} else {
head = prev
}
tail.Next = current
return head;
}
Javascript solution
var reverseBetween = function(head, left, right) {
if(head == null) {
return null;
}
if(left == right) {
return head;
}
let current = head, prev = null;
while(left > 1) {
prev = current;
current = current.next;
left;
right;
}
let tailPrev = prev, tail = current, iterator = null;
while(right > 0) {
iterator = current.next;
current.next = prev;
prev = current;
current = iterator;
right;
}
if(tailPrev != null) {
tailPrev.next = prev;
} else {
head = prev;
}
tail.next = current;
return head;
};
Let's dryrun our algorithm to see how the solution works.
Input: head = [1, 2, 3, 4, 5], left = 2, right = 4
head  [1, 2, 3, 4, 5]
Step 1: head == NULL
false
Step 2: left == right
2 == 4
false
Step 3: current = head, prev = null
current

head  [1, 2, 3, 4, 5]
Step 3: loop while left > 1
2 > 1
true
prev = current
current = current>next
current

prev  [1, 2, 3, 4, 5]
left
left = 1
right 
right = 3
Step 4: loop while left > 1
1 > 1
false
Step 5: tailPrev = prev
= 1
tail = current
= 2
iterator = NULL
Step 6: loop while right > 0
3 > 0
true
iterator = current>next
= 3
iterator

prev  [1, 2, 3, 4, 5]
current>next = prev
2>next = 1
prev = current
prev = 2
current = iterator
= 3
right
right = 2
prev   iterator
 
[1, 2, 3, 4, 5]

current
Step 7: loop while right > 0
2 > 0
true
iterator = current>next
= 4
iterator

[1, 2, 3, 4, 5]
current>next = prev
3>next = 2
prev = current
prev = 3
current = iterator
= 4
right
right = 1
prev   iterator
 
[1, 2, 3, 4, 5]

current
Step 8: loop while right > 0
1 > 0
true
iterator = current>next
= 5
iterator

[1, 2, 3, 4, 5]
current>next = prev
4>next = 3
prev = current
prev = 4
current = iterator
= 5
right
right = 0
prev   iterator
 
[1, 2, 3, 4, 5]

current
Step 9: loop while right > 0
0 > 0
false
Step 10: tailPrev != NULL
1 != NULL
true
tailPrev>next = prev
1>next = 4
Step 11: tail>next = current
2>next = 5
Step 12: return head
So we return the answer as [1, 4, 3, 2, 5].
Top comments (0)