20. [Linked List] Reverse Linked List II

92. Reverse Linked List IIMedium9.3K420Companies

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

Follow up: Could you do it in one pass?

Loading...LeetCode

Time: O(N)

Space: O(1)

/**
 * 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) {
    if (left === right) 
        return head;

    const dummy = new ListNode(-1);
    dummy.next = head;

    let start = head;
    let end = head;

    let curr = dummy;
    let cnt = 0;
    while (curr !== null) {
        if (cnt === left - 1) {
            start = curr;
        }

        if (cnt === right) {
            end = curr;
        }

        curr = curr.next;
        cnt++;
    }

    let h = start.next;
    let t = end.next;
    curr = h;
    let prev = t;
    while (curr !== null && curr !== t) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    start.next = prev;


    return dummy.next;
};