# 206. Reverse Linked List

### Leetcode

<https://leetcode.com/problems/reverse-linked-list/>

### 題目

Given the `head` of a singly linked list, reverse the list, and return *the reversed list*.

&#x20;

**Example 1:**

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

```
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
```

**Example 2:**

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

```
Input: head = [1,2]
Output: [2,1]
```

**Example 3:**

```
Input: head = []
Output: []
```

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

* **方法一**

用三個指標 last, before, pointer 達到反轉 linked list

```
var reverseList = function(head) {
    let pointer = head;
    let before = null;
    let last = null;
    while(pointer !== null) {
        last = before;
        before = pointer;
        pointer = pointer.next;
        before.next = last;
    }
    
    return before;
};
```

For example:

linked list = \[1, 2, 3];

<table><thead><tr><th width="150">Init</th><th></th><th></th><th></th></tr></thead><tbody><tr><td></td><td>1</td><td>2</td><td>3</td></tr><tr><td>last, before</td><td>pointer</td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td></tr></tbody></table>

<table><thead><tr><th width="150">First round</th><th></th><th></th><th></th></tr></thead><tbody><tr><td></td><td>1</td><td>2</td><td>3</td></tr><tr><td>last</td><td>before</td><td>pointer</td><td></td></tr><tr><td></td><td><code>before.next = last = null</code></td><td></td><td></td></tr></tbody></table>

<table><thead><tr><th width="150">Second round</th><th></th><th></th><th></th></tr></thead><tbody><tr><td></td><td>1</td><td>2</td><td>3</td></tr><tr><td></td><td>last = before</td><td>before</td><td>pointer</td></tr><tr><td></td><td></td><td><code>before.next = last = 1</code></td><td></td></tr></tbody></table>

<table><thead><tr><th width="150">Third round</th><th></th><th></th><th></th></tr></thead><tbody><tr><td></td><td>1</td><td>2</td><td>3</td></tr><tr><td></td><td></td><td>last = before</td><td>before</td></tr><tr><td></td><td></td><td></td><td><code>before.next = last = 2</code></td></tr></tbody></table>

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

Memory Usage: 40.5 MB, less than 83.92% of JavaScript online submissions for Reverse Linked List.

* **方法二**

紀錄 **前一個節點(prev)** 與 **後一個節點(next)** 以達到反轉列表的目的

範例：`head = [1,2]`

* 初始值

```javascript
prev = null
next = null
```

* 第一輪 - `head = 1`

```javascript
// 先保存下個節點
next = head.next // next = 2
// head 指向前一個節點
head.next = prev // 1 -> null
// 將 prev 移到目前節點
prev = head // prev = 1
// 將 head 移到下個節點
head = next // head = 2
```

* 第二輪 - `head = 2`

```javascript
// 先保存下個節點
next = head.next // next = null
// head 指向前一個節點
head.next = prev // 2 -> 1
// 將 prev 移到目前節點
prev = head // prev = 2
// 將 head 移到下個節點
head = next // head = null
```

做完兩輪後，會發現 `head` 已經到終點了，而整個反轉列表的開頭就是 `prev`

```
prev = 2 -> 1 -> null
```

```javascript
var reverseList = function (head) {
    let prev = null;
    let next = null;

    while (head) {
        next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }

    return prev;
};
```

* **方法三**

按照方法二的思路，但只是改成遞迴 recursion 的方式

```javascript
var reverseList = function (head, prev = null, next = null) {
    if (head) {
        next = head.next;
        head.next = prev;
        prev = head;
        head = next;
        return reverseList(head, prev, next);
    }

    return prev;
};
```

**參考資料**

{% embed url="<https://leetcode.wang/leetcode-206-Reverse-Linked-List.html>" %}
