LeetCode Swap Nodes in Pairs（兩兩交換鏈表節點）

一、題目描述

給定一個單鏈表，兩兩交換相鄰節點並返回新頭節點。不能修改節點值，只能改變指針，且使用常數額外空間。

範例： 1→2→3→4 → 2→1→4→3

二、解題思路：虛擬頭節點 + 指針操作

在頭節點前添加一個虛擬節點 dummy，統一處理頭節點交換邏輯。每次處理一對節點 node1、node2：

1. prev.next = node2
2. node1.next = node2.next
3. node2.next = node1
4. 移動 prev 到 node1（即下一對的前驅）

三、代碼實現（Python）

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        prev = dummy
        while prev.next and prev.next.next:
            node1 = prev.next
            node2 = prev.next.next
            # 交換
            prev.next = node2
            node1.next = node2.next
            node2.next = node1
            # 移動 prev
            prev = node1
        return dummy.next

# 測試
if __name__ == "__main__":
    # 構建 1->2->3->4
    n1, n2, n3, n4 = ListNode(1), ListNode(2), ListNode(3), ListNode(4)
    n1.next, n2.next, n3.next = n2, n3, n4
    res = Solution().swapPairs(n1)
    # 輸出 2 1 4 3
    while res:
        print(res.val, end=" ")
        res = res.next

四、複雜度分析

• 時間複雜度：O(N)，單次遍歷
• 空間複雜度：O(1)，只用常數指針

本題考察鏈表指針操作基本功，虛擬頭節點技巧極其實用。