Reverse Linked List II

Problem

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]

 

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Solution

/**
 * 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) {
    // create dummy head node (for case when left = 1)
    const first = new ListNode(0, head);

    // find node before left
    let before = first;
    for (let i = 1; i < left; i++) {
        before = before.next;
    }

    // reverse list
    let prev = null;
    let cur = before.next;
    for (let i = 0; i <= right - left; i++) {
        [cur.next, cur, prev] = [prev, cur.next, cur];
    }

    // attach last node in sub-list with next node in main-list
    before.next.next = cur;

    // attach first node in sub-list to previous node in main-list
    before.next = prev;

    return first.next;
};

First we find the node just before position left (hence why we need to dummy node in the case left = 1 where before wouldn't exist). Next, we reverse the sub-list in position [left, right]. Finally, we attach the reversed sub-list to the main-list and return the new head (ie. first.next).

For example, if head = [1, 2, 3, 4, 5], left = 2, and right = 4. We find that before is node 1 , reverse the sub-list [2, 3, 4] to get [4, 3, 2], and attach node 1 with node 5 / attach node 2 with node 5. This gives us [0, 1, 4, 3, 2, 5], where the desired result is the list without the first dummy node (ie. first.next).