嘿嘿～今天要來解一個大家都會碰到的經典題目：Reverse Linked List（反轉鏈結串列）。
想像一下，我們要把一列數字倒過來，這就像翻書一樣，把後面的翻到前面！
這題在面試中也很常見喔～但別擔心，這其實是一個簡單的小挑戰。
那我們就開始吧！

英文題目

Reverse Linked List

難度：Easy

題目描述：

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

給定一個單向鏈結串列的頭節點 head，將鏈結串列反轉，並返回反轉後的鏈結串列。

範例 1：

輸入： head = [1, 2, 3, 4, 5]

輸出： [5, 4, 3, 2, 1]

範例 2：

輸入： head = [1, 2]

輸出： [2, 1]

範例 3：

輸入： head = []

輸出： []

實作

反轉鏈結串列的解法其實可以很簡單，只需要用一個指針不斷把下一個節點「反向連接」回去，就像翻牌一樣，讓每一個節點都指向前一個節點。具體程式碼如下：

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null; // 前一個節點，初始為 null
    let current = head; // 當前節點，初始為 head

    while (current !== null) {
        let nextTemp = current.next; // 暫存下一個節點
        current.next = prev; // 將當前節點的指標指向前一個節點，反轉
        prev = current; // 移動前一個節點指針
        current = nextTemp; // 移動當前節點指針
    }

    return prev; // 最終 prev 指向的就是新的頭節點
}

解題心法

1. 用三個指針來反轉鏈結串列

   • prev：前一個節點，初始為 null，最終會變成新的頭節點。
   • current：當前正在處理的節點，從 head 開始遍歷。
   • nextTemp：暫時保存 current.next，因為我們在反轉指標時會丟失對原鏈結串列的引用。

2. 逐一反轉鏈結節點的指向

   每遍歷一個節點，我們就將其 next 指向前一個節點，這樣一步步反轉整個鏈結串列。

3. 遍歷整個鏈結串列直到 current 為空

   當 current 變成 null 時，反轉已經完成，最後的 prev 就是新的頭節點。

為什麼這樣處理？

這種方式最大化利用了鏈結串列的結構特性，通過一個簡單的遍歷和指標的調整，直接在原地完成了反轉。
由於只使用了常數級的額外空間，所以時間複雜度是 O(n)，空間複雜度是 O(1)。

本次要點：

• 使用三個指針（prev, current, nextTemp）來進行反轉操作。
• 每次將當前節點的指標指向前一個節點，逐步反轉鏈結串列。
• 最後返回 prev，即反轉後的頭節點。

這樣反轉完鏈結串列，是不是覺得其實很簡單呢？
每個挑戰就像這樣，一步一步來就能迎刃而解～
期待下次再與大家一起挑戰更多有趣的題目！≖‿≖