【图解 LeetCode】24：交换吧，链表！

你的名字 2022-09-10 02:19 121阅读 0赞

大家好呀，我是蛋蛋。

今天开搞**交换链表**，和反转链表一样，也是必考的“老熟人”。

话不多说，直接开工。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][b948de4a94c04f5e8f9320b0952de071.png]

### LeetCode 24：交换链表 ###

#### 题意 ####

两两交换链表相邻节点的值，返回交换后的链表。

#### 示例 ####

输入：head = \[1, 2, 3, 4\]  
输出： \[2, 1, 4, 3\]

#### 提示 ####

0 <= 链表节点数 <= 100  
0 <= Node.val <= 100

#### 题目解析 ####

水题，难度中等。

这道题要求不能只是单纯的改变节点内部得值，需要进行实际的节点交换。

和反转链表一样，这类链表题思维上没有难度，**就是每次从链表上截取两个节点进行交换**。

**主要是考察代码实现能力。**

这道题我用**带虚拟头节点的单链表**实现。

虚拟头节点（其实我以前都叫头节点，后来有臭宝和我说容易看混，我就叫虚拟头节点），可能很多人叫做**哨兵节点**，放在第一个元素的节点之前，数据域一般没意义。

#### 图解 ####

先建立一个带虚拟头节点的单链表。

![在这里插入图片描述][c4e4099e8baa4c83a5937aa741efc1d0.png]  
PS：此处代码为 Python（”代码实现“小节处有 Java 代码，下同）。

# 链表节点类
    class ListNode:
         def __init__(self, val=0, next=None):
             self.val = val
             self.next = next
    # 创建虚拟节点
    dummyHead = ListNode(-1)

因为每次要截取两个节点进行交换，初始建立 3 个指针 pre，p 和 q。

其中 pre 指向虚拟头节点，p 指向链表首节点，q 指向链表的第 2 个节点。

![在这里插入图片描述][fe547aac0bbc4f7e8b28b0838c6e58ff.png]

pre = dummyHead
    p = head
    q = p.next

节点两两交换主要分为 3 步。

第 1 步：pre 的后继指针 next 指向 q，即 pre.next = q。

![在这里插入图片描述][395d524e6a5b46f9ba2d114293529df6.png]  
第 2 步：p 的后继指针 next 指向 q 的后继节点，即 p.next = q.next。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
第 3 步：那就剩了 q 的后继指针 next 指向 p，即 q.next = p。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
所以第一次交换完，链表变成了：

![在这里插入图片描述][b2963343b8424d87a6caac6c80fd5790.png]

pre.next = q
    p.next = q.next
    q.next = p

接下来就是 pre、p 和 q 指针同时右移。

pre = p
    p = p.next
    q = p.next

继续重复上述 3 步操作。  
![在这里插入图片描述][51849aab784f4c6496c435f75beb9aad.png]  
本方法遍历一遍链表，时间复杂度为 O(n)，空间复杂度为 O(1)。

#### 代码实现 ####

Python 代码实现

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def swapPairs(self, head: ListNode) -> ListNode:
    
            # 空链表或者只有一个节点，直接返回
            if not head or head.next == None:
                return head
    
            # 创建虚拟节点
            dummyHead = ListNode(-1)
    
            # 初始化pre、p 节点
            pre = dummyHead
            p = head
    
            # 必须是节点数是偶数个的时候才能交换
            # 如果最后只剩下一个节点，即链表是奇数个节点，最后一个不用反转
            # 比如 head = [1,2, 3, 4, 5],输出 [2, 1, 4, 3, 5]
            while p and p.next:
                # 初始化 q 节点
                q = p.next
    
                # 交换节点 3 步走
                pre.next = q
                p.next = q.next
                q.next = p
                
                # 指针右移
                pre = p
                p = p.next
            
            # 返回链表
            return dummyHead.next

Java 代码实现

// 虚拟头结点
    class Solution {
      public ListNode swapPairs(ListNode head) {
    
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode prev = dummyNode;
    
        while (prev.next != null && prev.next.next != null) {
          ListNode temp = head.next.next; // 缓存 next
          prev.next = head.next;          // 将 prev 的 next 改为 head 的 next
          head.next.next = head;          // 将 head.next(prev.next) 的next，指向 head
          head.next = temp;               // 将head 的 next 接上缓存的temp
          prev = head;                    // 步进1位
          head = head.next;               // 步进1位
        }
        return dummyNode.next;
      }
    }

![在这里插入图片描述][6259588b81ea4f61b5bb61e7f2eae530.png]

图解交换链表到这就结束啦。

按照我的图解在纸上画一下加深印象，步骤不要出错。

在这我还是要叨叨叨，这类题思维上么的难度，考代码实现！臭宝们一定要多多练习，代码熟记，肌肉记忆。

当然辣，你们的**一键三连么么哒**也给我肌肉记忆起来呀～

我是帅蛋，我们下次见！

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/e1f80b4c636c445bbf2a4ac7c0cf7586.png
[b948de4a94c04f5e8f9320b0952de071.png]: /images/20220829/dd5a7145a8414854b6144f84b7320aaf.png
[c4e4099e8baa4c83a5937aa741efc1d0.png]: /images/20220829/b561a151cb3d4df5931830e7f5e6932c.png
[fe547aac0bbc4f7e8b28b0838c6e58ff.png]: /images/20220829/5f29b81483e745539634f0f75bf1a1a8.png
[395d524e6a5b46f9ba2d114293529df6.png]: /images/20220829/b6845ef799674b97bce753c9049a39cf.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/7a7035172c054a47925e382f5568ddf3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/63e6f6e52ddd4dd6b1a0c8dabb0b6a80.png
[b2963343b8424d87a6caac6c80fd5790.png]: /images/20220829/75ac2577411640f3a728277511518fe9.png
[51849aab784f4c6496c435f75beb9aad.png]: /images/20220829/6367fabc3c384ddfafcbdab10f79a3ef.png
[6259588b81ea4f61b5bb61e7f2eae530.png]: /images/20220829/a41d95c4b4bd401bb7f28fc253fe55f0.png