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.

Example 1:

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

Example 2:

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

Example 3:

Input: head = []
Output: []

解答

• 方法一

用三個指標 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];

Init
	1	2	3
last, before	pointer

First round
	1	2	3
last	before	pointer
	before.next = last = null

Second round
	1	2	3
	last = before	before	pointer
		before.next = last = 1

Third round
	1	2	3
		last = before	before
			before.next = last = 2

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]

• 初始值

prev = null
next = null

• 第一輪 - head = 1

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

• 第二輪 - head = 2

// 先保存下個節點
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

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 的方式

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;
};

參考資料

206. Reverse Linked List · leetcodeleetcode.wang