摘要

在開發中，鏈表結構經常出現在緩存淘汰、操作系統任務調度、或是 LRU 算法中，尤其是對節點位置的靈活操作更是鏈表的強項。LeetCode 第 328 題「奇偶鏈表」就給我們出了一個非常典型的“按位置分組再重組”的鏈表題目。今天我們用 Swift 帶你一步步理清它的邏輯，不僅實現，還要分析每一行代碼的作用。

描述

給定單鏈表的頭節點 head ，將所有索引為奇數的節點和索引為偶數的節點分別分組，保持它們原有的相對順序，然后把偶數索引節點分組連接到奇數索引節點分組之后，返回重新排序的鏈表。

第一個節點的索引被認為是 奇數 ， 第二個節點的索引為 偶數 ，以此類推。

請注意，偶數組和奇數組內部的相對順序應該與輸入時保持一致。

你必須在 O(1) 的額外空間復雜度和 O(n) 的時間復雜度下解決這個問題。

示例 1:

輸入: head = [1,2,3,4,5]
輸出: [1,3,5,2,4]

示例 2:

輸入: head = [2,1,3,5,6,4,7]
輸出: [2,3,6,7,1,5,4]

提示:

• n == 鏈表中的節點數
• 0 <= n <= 104
• -106 <= Node.val <= 106

題解答案

我們可以把鏈表分成兩條線：

• 一條是奇數索引節點組成的鏈；
• 一條是偶數索引節點組成的鏈；

我們遍歷一遍，把這兩條鏈連起來就搞定了。因為我們只用了幾個額外指針，空間上是 O(1)；每個節點最多訪問一次，時間上是 O(n)。

題解代碼分析

class ListNode {var val: Intvar next: ListNode?init(_ val: Int) {self.val = valself.next = nil}
}func oddEvenList(_ head: ListNode?) -> ListNode? {guard let head = head, let next = head.next else {return head  // 如果鏈表為空或只有一個節點，直接返回}var odd = head             // 奇數位置的起點var even = next            // 偶數位置的起點let evenHead = even        // 保存偶數起點，最后連接用while let nextOdd = even.next {odd.next = nextOddodd = nextOddeven.next = nextOdd.nextif let nextEven = even.next {even = nextEven}}odd.next = evenHead  // 把奇數鏈的尾巴接上偶數鏈的頭return head
}

分段講解

1. 初始化階段：

guard let head = head, let next = head.next else { return head }

判斷是否為空鏈表或僅有一個節點，不用處理，直接返回。

2. 定義指針：

var odd = head
var even = next
let evenHead = even

奇鏈和偶鏈分別以 odd 和 even 為頭，注意我們還要保留 evenHead，后面連接會用到。

3. 鏈表分離過程：

while let nextOdd = even.next {odd.next = nextOddodd = nextOddeven.next = nextOdd.nextif let nextEven = even.next {even = nextEven}
}

每一輪迭代，我們都讓 odd 跳兩個節點，even 也跳兩個。直到鏈表末尾。遍歷中奇偶節點自動分組完成。

4. 拼接兩個鏈表：

odd.next = evenHead

把奇數鏈表的尾部，接上偶數鏈表的頭部。

示例測試及結果

我們來測試下：

// 構建測試鏈表 [1,2,3,4,5]
let node1 = ListNode(1)
let node2 = ListNode(2)
let node3 = ListNode(3)
let node4 = ListNode(4)
let node5 = ListNode(5)node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5// 調用函數
let newHead = oddEvenList(node1)// 打印結果
var current = newHead
while current != nil {print(current!.val, terminator: " ")current = current?.next
}
// 輸出：1 3 5 2 4

時間復雜度

整條鏈表我們只遍歷了一次，每個節點訪問不超過兩次。

• 時間復雜度： O(n)，其中 n 是鏈表的長度。

空間復雜度

只用了固定數量的指針變量，沒有創建新的節點或結構。

• 空間復雜度： O(1)，常數空間。

總結

這道題的關鍵在于兩個鏈表交替構建，同時維護好頭尾指針。在實際開發中，鏈表的拆分與重組很常見，比如分頁展示、批量處理等功能也可能需要對數據鏈按規則拆分。

通過這道題，不僅練習了鏈表的結構操作，還能加深對“指針引用不等于復制”的理解。如果你能寫出無 bug 的鏈表處理代碼，那你對 Swift 的指針語義已經很熟練了！