92. Reverse Linked List II

Leetcode

https://leetcode.com/problems/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]

解答

• 方法一

把整個 linked list 分成三部分進行處理，[正常排序] - [逆排序] - [正常排序]

For example:

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

最終答案是 1 -> 4 -> 3 -> 2 -> 5 ，我們主要要做的就是把中間的 2, 3, 4 逆排序過來

var reverseBetween = function(head, left, right) {
    if(head === null) return null;
    
    let prev = null;
    let curr = head;
    // 處理左半邊的正常排序
    while(left > 1) {
        prev = curr;
        curr = curr.next;
        left--;
        right--;
    }
    
    // connect 紀錄左邊正常排序的連接點，example 中為 1
    const connect = prev;
    // tail 紀錄逆排序完後，應該在逆排序中最右邊的那個點，example 中為 2
    let tail = curr;
    
    // 利用 next 來保存 curr.next 的值，最後將 curr 移動到下一個元素
    // 不然 curr.next 會在 curr.next = prev 賦值時被指向到 prev 所覆蓋，導致無窮迴圈
    let next = null;
    // 將中間的排序整個倒轉過來 (變成 4 -> 3 -> 2)
    while(right > 0) {
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next; 
        right--;
    }
    
    // example 中，逆排序完之後，prev 等於 4、curr 等於 5
    // 如果 connect 存在，connect 指向為逆排序中最右邊的值，example 中即 1 -> 4
    if(connect !== null) {
        connect.next = prev;
    } else {
        // 如果 connect 不存在，即代表一開始的就是要進行逆排序
        // 所以 head 就會是逆排序中最右邊的元素
        head = prev;
    }
    
    // example 中即代表 tail: 2 -> curr: 5
    tail.next = curr;
    return head;
};

Runtime: 68 ms, faster than 89.41% of JavaScript online submissions for Reverse Linked List II.

Memory Usage: 38.9 MB, less than 78.24% of JavaScript online submissions for Reverse Linked List II.

測資

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

output = [1,4,3,2,5];