24. Swap Nodes In Pairs
MediumDescription
給定一個鏈結串列，兩兩交換相鄰的節點，回傳交換後的頭節點。必須實際交換節點，不能只改值。
Example:
Input: head = [1,2,3,4] Output: [2,1,4,3]
Intuition#
核心思路：每次處理兩個節點的交換，然後遞迴或迭代處理剩餘部分。
- 這是 k-Group Reverse (LC 25) 在 k=2 時的特例
- 每次取兩個節點交換，需要注意指針的重新連接
- 遞迴解法最直觀：交換前兩個，然後遞迴處理剩餘
Approaches#
1: Recursive#
- 概念: 交換前兩個節點，第一個節點的 next 指向遞迴處理後的結果
- 時間複雜度:
O(n) - 空間複雜度:
O(n)- 遞迴堆疊
class Solution {
fun swapPairs(head: ListNode?): ListNode? {
if (head?.next == null) return head
val first = head
val second = head.next
first.next = swapPairs(second?.next)
second?.next = first
return second
}
}⭐2: Iterative with Dummy Head#
- 概念: 使用 dummy 節點，每次取 prev 後面的兩個節點交換，然後移動 prev
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun swapPairs(head: ListNode?): ListNode? {
val dummy = ListNode(0)
dummy.next = head
var prev: ListNode? = dummy
while (prev?.next != null && prev.next?.next != null) {
val first = prev.next!!
val second = first.next!!
// 交換
first.next = second.next
second.next = first
prev.next = second
// 移動 prev 到下一對的前面
prev = first
}
return dummy.next
}
}🔑 Takeaways#
- Pattern: 鏈結串列的成對操作，是 k-Group 操作的基礎。遞迴解法簡潔但空間 O(n)
- 關鍵技巧: Dummy head 處理頭部交換；迭代時 prev 指向每一對的前一個節點，交換後 prev 移到交換完的第二個節點（原本的第一個）