今天是紀錄LeetCode解題的第二十四天

第二十四題題目：Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

給定一個鏈結串列，交換每兩個相鄰的節點，必須在不修改節點值的情況下（即只能修改節點本身）解決問題

解題思路

假設prev → A → B → next，交換AB變成prev → B → A → next
表示需要：

• A.next指向next
• B.next指向A
• prev.next指向B

這樣就順利完成交換了

程式碼

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        while prev.next and prev.next.next: #確保至少有兩個節點
            first = prev.next
            second = prev.next.next

            first.next = second.next
            second.next = first
            prev.next = second

            prev = first

        return dummy.next

變數意義

• prev：當前要交換的這一對的「前一個節點」（最開始是 dummy）
• first：要交換的第一個節點（原本在前面)
• second：要交換的第二個節點（原本在後面)

執行過程

總結

為什麼prev = first，而不是prev = second
交換後first(原本的前節點)變成該組的「尾」，它的 next 剛好指向下一組的第一個節點，因此把prev設為first，下一輪prev.next就會是下一對的第一個節點

奇數個節點
如果鏈結串列長度是奇數，例如1→2→3，第一次交換後為2→1→3，然後prev = 1，下一次檢查prev.next(也就是3)和 prev.next.next(是 None)，條件不成立，迴圈停止，最後一個節點保留不動