Reverse Linked List II

Given a singly linked list with `n` nodes and two positions, `left` and `right`, the objective is to reverse the nodes of the list from `left` to `right`. Return the modified list.

Given a singly linked list with n nodes and two positions, left and right, the objective is to reverse the nodes of the list from left to right. Return the modified list.

Statement

Given a singly linked list with n nodes and two positions, left and right, the objective is to reverse the nodes of the list from left to right. Return the modified list.

Constraints

• 1 ≤ n ≤ 500
• −5000 ≤ node.data ≤ 5000
• 1 ≤ left ≤ right ≤ n

Examples

Example 1

Input: head = [1, 2, 3, 4, 5] left = 2, right = 4

Explanation: The nodes from position 2 to 4 are [2, 3, 4]. Reversing them gives [4, 3, 2]. The rest of the list stays in place.

Output: [1, 4, 3, 2, 5]

Example 2

Input: head = [5, 1, 3, 8] left = 1, right = 4

Explanation: The nodes from position 1 to 4 cover the entire list [5, 1, 3, 8]. Reversing the whole list gives [8, 3, 1, 5].

Output: [8, 3, 1, 5]

function linkedListII(head, left, right) {

    let leftElement = head;
    let beforeLeft = null;
    let rightElement = head;

    // Find leftElement
    for (let i = 1; i < left; i++) {
        beforeLeft = leftElement;
        leftElement = leftElement.next;
        rightElement = rightElement.next;
    }

    // Find rightElement
    for (let j = 0; j < right - left; j++) {
        rightElement = rightElement.next;
    }

    // Reverse left -> right
    let [prev, curr] = reverseKelements(
        leftElement,
        right - left + 1
    );

    // Old leftElement is now the last node
    leftElement.next = curr;

    // If we reversed from the head
    if (left === 1) {
        return prev;
    }

    // Connect node before left to reversed portion
    beforeLeft.next = prev;

    return head;
}

or

var reverseBetween = function (head, left, right) {
    function reverseK(head, k = 2) {
        let prev = null;
        let curr = head;
        let next = null;

        while (curr !== null && k > 0) {

            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
            k--;
        }

        return [prev, curr];
    }

    let dummy = new ListNode(0, head);

    let leftPos = dummy;

    for (let i = 1; i < left; i++) {
        leftPos = leftPos.next;
    }


    let oldHead = leftPos.next;

    let [reverseHead, nextElement] = reverseK(leftPos.next, right - left + 1);

    leftPos.next = reverseHead;

    oldHead.next = nextElement;



    return dummy.next;

};