# 【LeetCode刷題】【演算法學習筆記】206. Reverse Linked List
* 學習時間：2025/02/07 (Fri.)
* **題目連結（美服）：** [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/description/)
* **題目連結（國服）：**[206. 反轉鏈表](https://leetcode.cn/problems/reverse-linked-list/description/)
* **題目標籤：** ==陣列== ==雙指針== ==排序==

### A. 題目
---
>Given the head of a singly linked list, reverse the list, and return the reversed list.

### B. 題意（中文）
---
>给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

### C. 參考程式碼
---
**靈神題解 (reference:[灵茶山艾府](https://leetcode.cn/problems/reverse-linked-list/))**

:::spoiler 思路

* 遍歷鏈結串列，逐步將每個節點的指向反轉，並使用三個指標來維護遍歷過程。
1. 使用三個指標
在反轉鏈結串列的過程中，我們維護三個指標：
* pre（前一個節點）：用來保存已反轉部分的最後一個節點。
* cur（當前節點）：目前正在處理的節點。
* nxt（下一個節點）：用來暫存下一個還未處理的節點，防止指向丟失。

2. 逐步反轉指向
**在 ==while cur:== 迴圈內，我們對每個節點進行以下操作：**
1. 保存下一個節點，因為我們即將改變 ==cur.next==，所以要先存下 cur.next 的原始值，避免丟失：
`nxt = cur.next`

2. 反轉當前節點的指向，讓 ==cur.next== 指向 pre，這樣該節點就與原本的順序斷開，並指向已反轉的部分：
`cur.next = pre`

3. 更新 ==pre== 和 ==cur==，準備處理下一個節點：

        pre = cur  # 將當前節點變成已反轉部分的最後一個節點
        cur = nxt  # 移動到下一個未處理的節點

3. 迴圈結束後返回 pre
當 cur 變成 None（代表所有節點都反轉完畢），此時 pre 就是新的頭節點，直接返回：

`return pre`

:::

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 目標： null <- pre <- cur
        # 初始化：前一個節點、當前節點
        # pre（表示前一個節點）一開始設為 None，因為新鏈結尾巴會指向 None
        pre = None
        cur = head
        
        # 當 cur 為 None 時，代表整個串列已處理完畢，迴圈結束 
        while cur:
            # 儲存下一個節點
            # 因為 cur.next 之後會被改變，先存起來，以免失去對原串列的連結
            nxt = cur.next
            # 讓連結反轉指向上一個節點
            # 當前節點 cur 的 next 指向 pre
            cur.next = pre

            # 更新 pre 和 cur 並向右走，準備處理下一個節點
            pre = cur
            cur = nxt
        # 返回新的 head 
        # 新的頭節點（原本的最後一個節點）
        return pre

#### 🤖 **複雜度**
這個方法的時間複雜度是 O(n)，因為它遍歷了一次鏈結串列。空間複雜度是 O(1)，因為它只用了幾個變數 (pre, cur, nxt)，沒有額外開新空間。