206. Reverse Linked List

這是一個「鏈結串列（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]

在這個題目中，要求將串接而成的鏈結串列「倒序」排列，但因為鏈結串列「相連」的特性，需要思考怎麼操作才能實現倒序的結果。

開始實作

在理解完題目與條件之後，那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程：

方法 ①：交換法

第一種可以透過交換的方式將指針的方向倒序，可以參考下面這張由「GeeksforGeeks」提供的示意圖：

我們需要交換的重點在於將「指向下一個 head.next」改成指向「前一個節點 prev」：

head.next = prev

但是為了實現所有的點，我們需要保存一些原有的資訊。因此操作上對每一個點來說，有三個指針：

• head：指向自己
• head.next：指向下一個
• prev：指向前一個

我們需要將三個指針交換成：

• head：指向自己 → 指向下一個（head.next）
• head.next：指向前一個（prev）
• prev：指向前一個 → 指向自己（head）

那我們先用 Python 實作看看

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        while head:
            next = head.next
            head.next = prev
            prev = head
            head = next
        return prev

也可以用 JavaScript 復刻一次

var reverseList = function(head) {
    let prev = null;
    while (head) {
        next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev; 
};

不過其實這裡在做的是「三數交換」，可以不需要 temp 變數，簡化為以下的寫法即可：

# Python
while: head.next, prev, head = prev, head, head.next

# JavaScript
while (head) [head.next, prev, head] = [prev, head, head.next];

方法 ②：遞迴（recursion）

第二種方法是遞迴（recursion），概念是「先把下一個記起來，將自己反過來指向前一個」，然後下一個持續執行直到沒有下一個為止。因為每個點的步驟是類似，因為可以將下一個持續執行的動作利用遞迴實現。

那我們先用 Python 實作看看

class Solution:
    def reverseList(self, head: Optional[ListNode], prev=None) -> Optional[ListNode]:
        if not head: return prev
        next = head.next # 先把下一個記起來
        head.next = prev # 將自己反過來指向前一個
        return self.reverseList(next, head)

也可以用 JavaScript 復刻一次

var reverseList = function(head, prev=null) {
    if(!head) return prev;
    let next = head.next; // 先把下一個記起來
    head.next = prev; // 將自己反過來指向前一個
    return reverseList(next, head);
};

反思沉澱

這題就開始導入鏈結串列（Linked List）的題目，關於鏈結串列必須了解其定義、特性跟一些常見的操作方法（包含「新增」、「刪除」或是「倒轉」之類的動作）。而「方法 ②：遞迴（recursion）」的方法，遞迴是許多程式開發的第一個或第二個可能遇到的門檻，也蠻適合的在這個題目中感受看看的。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目，適合作為你下一個嘗試的練習：

• 92. Reverse Linked List II
• 234. Palindrome Linked List

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。