24. Swap Nodes in Pairs

前面我們著重在「資料結構」的議題上做了不少的討論，從大家的熟悉的陣列開始，算是走過一輪常見的資料結構。接下來，我們要進入另外一個面向的思維，從條件判斷與重複回圈的流程控制下手的「演算法」題目。在前面的練習中，有一個出場很多次的演算法「遞迴（Recursion）」，而遞迴其實很常搭配鏈結串列或是樹的資料結構使用。所以我們就挑選一題鏈結串列中看起來跟交換有關的題目。

先看一下題目描述

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.)

再搭配範例理解題目

• Example 1:

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

這個題目看起來是「兩兩交換」的問題，但因為他是鏈結串列的資料結構，所以實際上是「兩兩節點的數值交換」，背後隱含的是「兩兩節點的鏈結」不變。

開始實作

在理解完題目與條件之後，那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程：

方法 ①：迭代兩兩交換

第一種方法其實就很直覺，每次記錄兩個節點數值交換，之後再將兩個節點指標往後移動。注意，「指標往後移動」這裡用原本節點的鏈結即可。

用 Python 實作一次

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head
        prev = head
        cur  = head.next

        while prev and cur:
            # 「兩兩節點的數值交換」
            temp = prev.val;
            prev.val = cur.val;
            cur.val = temp;

            if not cur.next or not cur.next.next:
                break

            # 「兩兩節點的鏈結」
            prev = cur.next;
            cur  = cur.next.next;     
        
        return head

也可以用 JavaScript 復刻一次

var swapPairs = function(head) {
    if(head == null || head.next == null) return head;
    var prev = head;
    var cur  = head.next;

    while(prev != null && cur != null){
        // 「兩兩節點的數值交換」
        var temp = prev.val;
        prev.val = cur.val;
        cur.val = temp;

        if(cur.next == null || cur.next.next == null)
            break;
        
        // 「兩兩節點的鏈結」
        prev = cur.next;
        cur  = cur.next.next;     
    }   
    return head;
};

方法 ②：遞迴

稍微拆解一下題目，其實題目要做的事情是以兩個點為一組，完成以下操作：

• 將第一個點（head）指向第三個點（head.next.next）
• 將第二個點（head.next）指向第一個點（head）

可能會出類似以下的樣子：

head.next = head.next.next
head.next.next = head

但這樣寫可能會造成第二個點（head.next）被改寫，而失去原本的期待，因此需要先暫存第二的點：

next = head.next
head.next = next.next
next.next = head

以上這樣完成了一組的操作，為了讓所有點都可以依照此規則，可以加入遞迴的方法迭代：

next = head.next
head.next = swapPairs(next.next)
next.next = head

用 Python 實作一次

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head
        next = head.next # next 指向第二個點
        head.next = self.swapPairs(next.next) # head 指向第三個點
        next.next = head # next.next 指向第一個點
        return next

也可以用 JavaScript 復刻一次

var swapPairs = function(head) {
    if (!head || !head.next) return head; 
    let next = head.next; // next 指向第二個點
    head.next = swapPairs(next.next); // head 指向第三個點
    next.next = head; // next.next 指向第一個點
    return next;
};

反思沉澱

這個題目挑選了一題鏈結串列當中的交換操作，鏈結串列跟交換的概念都不難，很容易就可以用迴圈的方法實現。只是如果我們開場所提：「要寫出會動的程式不難，但要寫出漂亮的程式有點難度」，所以從這個基礎版本刻意優化的遞迴優化，就是這題想要給大家一起體驗的過程。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目，適合作為你下一個嘗試的練習：

• 25. Reverse Nodes in k-Group
• 1721. Swapping Nodes in a Linked List

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。