206. Reverse Linked List

📘 題目敘述

給你一個單向 linked list 的頭節點 head，請你把 linked list 反轉，並回傳反轉後的 linked list。

條件限制

• linked list 的節點數量在範圍 [0, 5000]。
• -5000 <= Node.val <= 5000。

🧠 解題思路

我的做法是分成兩段：

1. 先走訪原本的 linked list，把每個節點的數值依序丟進 stack。
   • 因為 stack 是後進先出，所以最後 stack.top() 會是原本 linked list 的最後一個值。
2. 再用 dummy 當假頭、tail 當尾巴指標，從 stack 一個一個拿出來建新節點接到尾端。
   • 這樣建出來的新 linked list 順序就會是反過來的。

最後回傳 dummy.next，就能得到反轉後的新 linked list。

所有變數

• head：走訪原 linked list 用的指標（一路往後移動）
• nums：stack<int>，存放走訪到的所有節點數值
• dummy：答案 linked list 的假頭節點
• tail：答案 linked list 目前的尾巴指標（用來接新節點）

🪜 主要流程步驟

1. 把原 linked list 的值全部推進 stack

• 用 while (head) 走完整條串列
• 每次：
  • nums.push(head->val)
  • head = head->next

2. 建立答案串列的假頭與尾巴指標

• ListNode dummy(0);
• ListNode* tail = &dummy;

3. 從 stack 取值，依序建立新節點接到尾端

• while (!nums.empty())：
  • tail->next = new ListNode(nums.top());
  • tail = tail->next;
  • nums.pop();

4. 回傳反轉後的新串列頭

• return dummy.next;

💻 程式碼實作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        stack<int> nums;
        while (head) {
            nums.push(head->val);
            head = head->next;
        }
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (!nums.empty()) {
            tail->next = new ListNode(nums.top());
            tail = tail->next;
            nums.pop();
        }
        return dummy.next;
    }
};

🔗 題目連結

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