題目
#

leetcode 206 - Reverse Linked List (題目說明請點連結)

題目簡述
#

反轉一個單向鏈表。

範例
#

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Explanation: 將鏈表 1→2→3→4→5 反轉為 5→4→3→2→1。

Example 2:

Input: head = [1,2]
Output: [2,1]
Explanation: 將鏈表 1→2 反轉為 2→1。

Example 3:

Input: head = []
Output: []
Explanation: 空鏈表反轉後仍為空鏈表。

解題思路
#

這題要求我們反轉一個單向鏈表。我們需要使用三個指針來逐步改變節點的指向，將每個節點的 next 指針指向前一個節點。

解法
#

迭代反轉法（Iterative Approach）

使用三個指針：node（前一個節點）、head（當前節點）、temp（下一個節點）
在每次迭代中：
- 保存下一個節點到 temp
- 將當前節點的 next 指向前一個節點
- 移動指針到下一個位置
最終返回反轉後的頭節點

步驟
#

初始化：
- node = null（前一個節點，初始為空）
迭代反轉：
- 當 head != null 時繼續迴圈
- temp = head.next：保存下一個節點
- head.next = node：將當前節點指向前一個節點
- node = head：前一個節點變為當前節點
- head = temp：當前節點變為下一個節點
返回結果：
- 返回 node（反轉後的頭節點）

核心邏輯
#

while (head != null) {
    ListNode temp = head.next;    // 保存下一個節點
    head.next = node;             // 反轉指向
    node = head;                  // 移動前一個指針
    head = temp;                  // 移動當前指針
}

指針變化說明
#

node：指向前一個節點，用於連接
head：指向當前節點，需要反轉其指向
temp：保存下一個節點，防止丟失

例子說明
#

head = [1,2,3]

步驟	node	head	temp	head.next	操作說明
初始化	null	1→2→3	-	-	設定初始狀態
第1輪	null	1→2→3	2→3	null	保存temp=2→3，反轉1指向null
	1	2→3	2→3	1	node=1，head=2→3
第2輪	1	2→3	3	1	保存temp=3，反轉2指向1
	2→1	3	3	2→1	node=2→1，head=3
第3輪	2→1	3	null	2→1	保存temp=null，反轉3指向2
	3→2→1	null	null	3→2→1	node=3→2→1，head=null
最終結果	3→2→1	null	-	-	返回node，鏈表反轉完成

完整程式碼
#

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode node = null;

        while (head != null) {
            // 保存下一個節點，防止丟失
            ListNode temp = head.next;
            // 將當前節點的next指向前一個節點，實現反轉
            head.next = node;
            // 前一個節點變為當前節點
            node = head;
            // 當前節點變為下一個節點
            head = temp;
        }
        
        // 返回反轉後的頭節點
        return node;
    }
}