題目
#

題目簡述
#

給一個單向鏈表的頭節點 head，請將鏈表重新排列，使得鏈表變成：L0 → L1 → L2 → ... → Ln-1 → Ln 變成 L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...
注意：不能修改節點的值，只能改變節點的連接順序。

範例
#

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

解題思路
#

這題要求我們重新排列鏈表，使得第一個節點連接到最後一個節點，第二個節點連接到倒數第二個節點，以此類推。我們可以使用快慢指針找到鏈表中點，然後反轉後半部分，最後合併兩個鏈表。

解法
#

使用快慢指針找到鏈表的中點
將鏈表從中點分割成兩個部分
反轉後半部分鏈表
合併兩個鏈表，交替連接節點

步驟
#

尋找中點：
- 使用快慢指針，快指針每次移動兩步，慢指針每次移動一步
- 當快指針到達末尾時，慢指針指向中點
分割鏈表：
- 將鏈表從中點分割成兩個部分
- 前半部分保持不變，後半部分需要反轉
反轉後半部分：
- 使用反轉鏈表的標準方法
- 維護 prev、curr、next 三個指針
合併鏈表：
- 交替連接兩個鏈表的節點
- 保存下一個節點的引用，避免丟失

例子說明
#

head = [1,2,3,4]

步驟	操作	鏈表狀態	說明
初始化	開始	`1 → 2 → 3 → 4`	原始鏈表
第 1 步	快慢指針找中點	`1 → 2 → 3 → 4`	慢指針指向 2，快指針指向 4
第 2 步	分割鏈表	`1 → 2` 和 `3 → 4`	從節點 2 後分割
第 3 步	反轉後半部分	`1 → 2` 和 `4 → 3`	後半部分反轉
第 4 步	合併鏈表	`1 → 4 → 2 → 3`	交替連接節點

最終結果： [1,4,2,3]

重排序過程說明：

步驟 1：使用快慢指針找到中點（節點 2）
步驟 2：將鏈表分割為 [1,2] 和 [3,4]
步驟 3：反轉後半部分得到 [4,3]
步驟 4：交替合併：1 → 4 → 2 → 3

完整程式碼
#

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 void reorderList(ListNode head) {
        // 邊界條件：如果鏈表為空或只有一個節點，直接返回
        if(head == null || head.next == null) {
            return;
        }

        ListNode fast = head, slow = head;

        // 1. 快慢指針找中點
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. 反轉後半鏈表
        ListNode prev = null, curr = slow.next;
        while(curr != null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        // 斷開中點，將鏈表分成兩個部分
        /*
        
        1 → 2 → 3 → null
        5 → 4 → null
        
         */
        slow.next = null;

        ListNode first = head, second = prev;

        // 3. 合併兩個鏈表
        while(second != null){
            ListNode tmp1 = first.next;
            ListNode tmp2 = second.next;

            first.next = second;
            second.next = tmp1;

            first = tmp1;
            second = tmp2;
        }
    }
}