[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;
}

8 thoughts on “[Programming Problem] Reverse Linked List II

  1. I really wanted to send a brief word so as to appreciate you for all the awesome advice you are placing here. My time consuming internet look up has now been recognized with high-quality ideas to go over with my companions. I ‘d state that that we visitors actually are rather endowed to live in a notable site with so many awesome individuals with good techniques. I feel extremely grateful to have discovered the weblog and look forward to really more brilliant minutes reading here. Thanks a lot once again for a lot of things.

  2. I have to show my appreciation for your generosity supporting those people who absolutely need help on this particular study. Your personal commitment to passing the solution all-around was quite helpful and has all the time made most people just like me to arrive at their targets. Your personal insightful hints and tips indicates a whole lot to me and even further to my office workers. Best wishes; from everyone of us.

  3. Thank you for all of your labor on this site. Gloria really likes working on investigation and it’s obvious why. My spouse and i learn all of the dynamic medium you give both interesting and useful guides by means of the website and cause response from others on that idea so our princess is without a doubt becoming educated a lot. Take pleasure in the remaining portion of the year. You’re conducting a brilliant job.

  4. I want to express my respect for your generosity for visitors who really need assistance with this one issue. Your special commitment to passing the solution all-around appears to be quite effective and have constantly encouraged somebody like me to achieve their desired goals. Your entire valuable information implies much a person like me and even more to my office colleagues. Thanks a lot; from each one of us.

  5. I wish to express some appreciation to you just for bailing me out of this problem. Because of looking throughout the the web and finding recommendations which are not pleasant, I was thinking my life was well over. Existing without the approaches to the difficulties you’ve sorted out by way of your main article is a serious case, as well as ones that could have negatively affected my career if I had not noticed your site. Your skills and kindness in maneuvering all the things was helpful. I’m not sure what I would have done if I had not discovered such a subject like this. I can at this time look forward to my future. Thanks for your time so much for this impressive and result oriented help. I won’t think twice to propose the website to anybody who should receive recommendations about this problem.

  6. I wish to voice my respect for your kindness for folks who have the need for guidance on this important concern. Your personal dedication to passing the solution all over came to be especially good and has truly helped women just like me to arrive at their targets. Your new insightful guide can mean a lot to me and much more to my fellow workers. Best wishes; from everyone of us.

Leave a Reply

Your email address will not be published.