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] |
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]
Problem Link
The algorithm is as follows:-
- Segregate nodes into
- Reverse the nodes_to_reverse (recursive algorithm)
- Merge
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function(head, left, right) {
// 1. Segregate nodes into <left - nodes_to_reverse - right>
let leftNode = null, reverseNode = null, rightNode = null;
let i = 1;
let curr = head;
while (curr !== null) {
let tmp = curr;
curr = curr.next;
tmp.next = null;
if ( i < left ) {
if ( leftNode === null ) leftNode = tmp
else getEnd(leftNode).next = tmp
} else if ( i >= left && i <= right ) {
if ( reverseNode === null ) reverseNode = tmp
else getEnd(reverseNode).next = tmp
} else {
if ( rightNode === null ) rightNode = tmp
else getEnd(rightNode).next = tmp
}
i++;
}
// 2. Reverse the nodes_to_reverse
const reversedNodes = reverse(reverseNode);
// 3. Merge <left - reversed(nodes_to_reverse) - right>
let ret = null;
if (leftNode !== null) ret = leftNode;
if (ret === null) ret = reversedNodes
else getEnd(ret).next = reversedNodes
if (ret === null) ret = rightNode
else getEnd(ret).next = rightNode
return ret;
};
var getEnd = function(head) {
let tmp = head;
while (tmp.next !== null) tmp = tmp.next;
return tmp;
}
var reverse = function(head) {
if (head === null || head.next === null) return head;
const ret = reverse(head.next);
let curr = ret;
while (curr.next !== null) curr = curr.next;
head.next = null;
curr.next = head;
return ret;
} |
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function(head, left, right) {
// 1. Segregate nodes into <left - nodes_to_reverse - right>
let leftNode = null, reverseNode = null, rightNode = null;
let i = 1;
let curr = head;
while (curr !== null) {
let tmp = curr;
curr = curr.next;
tmp.next = null;
if ( i < left ) {
if ( leftNode === null ) leftNode = tmp
else getEnd(leftNode).next = tmp
} else if ( i >= left && i <= right ) {
if ( reverseNode === null ) reverseNode = tmp
else getEnd(reverseNode).next = tmp
} else {
if ( rightNode === null ) rightNode = tmp
else getEnd(rightNode).next = tmp
}
i++;
}
// 2. Reverse the nodes_to_reverse
const reversedNodes = reverse(reverseNode);
// 3. Merge <left - reversed(nodes_to_reverse) - right>
let ret = null;
if (leftNode !== null) ret = leftNode;
if (ret === null) ret = reversedNodes
else getEnd(ret).next = reversedNodes
if (ret === null) ret = rightNode
else getEnd(ret).next = rightNode
return ret;
};
var getEnd = function(head) {
let tmp = head;
while (tmp.next !== null) tmp = tmp.next;
return tmp;
}
var reverse = function(head) {
if (head === null || head.next === null) return head;
const ret = reverse(head.next);
let curr = ret;
while (curr.next !== null) curr = curr.next;
head.next = null;
curr.next = head;
return ret;
}