昨天介紹完 Linked List，今天來看看實際的應用吧！
這題算是鏈結串列的經典入門題之一

206. Reverse Linked List

題目

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

給定一個單向鏈結串列的頭節點 head，請將整條鏈結串列反轉後回傳。

例如：

Input: 1 → 2 → 3 → 4 → 5 
Output: 5 → 4 → 3 → 2 → 1

Reverse Linked List

分析

陣列反轉時，我們可以透過交換元素來完成：

1 2 3 4 5
↓
5 4 3 2 1

但 Linked List 並沒有索引（Index）的概念，因此無法直接透過下標交換。
我們必須改變每個節點的 next 指向。

原本：

1 → 2 → 3 → nullptr

希望變成：

nullptr ← 1 ← 2 ← 3

也就是：

3 → 2 → 1 → nullptr

單向鏈結串列每個節點只知道「下一個是誰」(next),不知道「前一個是誰」。

這代表一件麻煩的事:
只要把 cur->next 改指向前一個節點,原本通往後半段串列的路就被切斷了,再也找不到原本的下一個節點在哪裡。

所以整題的關鍵,就是在改變方向之前,先把「原本的下一個節點」記下來

nextNode = cur->next;

可以寫成以下流程

1. 保存下一個節點
2. 反轉指標
3. prev 往前走
4. cur 往前走

程式碼

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur = head;

    while (cur != nullptr) {
        ListNode* next = cur->next;  // 先存下下一個節點,不然改指標後就找不到了
        cur->next = prev;            // 把箭頭反過來,指向前一個
        prev = cur;                  // prev 往前移一格
        cur = next;                  // cur 也往前移一格
    }

    return prev;  // cur 變成 NULL 時,prev 停在原本的最後一個節點,即新的頭
}

以 1→2→3 為例,追蹤每一輪 prev / cur 的變化:

最後回傳 prev,也就是 3,此時串列變成 3→2→1→NULL,反轉完成

複雜度分析

時間複雜度 : O(n) - 每個節點只會被拜訪一次，因此總共需要走訪 n 個節點