LeetCode 双刀流：24. Swap Nodes in Pairs

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 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。