# 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*.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/02/19/rev2ex2.jpg)

```
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]
```

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

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

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];
```
