[Programming 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.
 
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:-

  1. Segregate nodes into
  2. Reverse the nodes_to_reverse (recursive algorithm)
  3. 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;
}

Leave a Reply

Your email address will not be published.