15、两两交换链表的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

示例 2：

**输入：**head = [] 输出：[]

示例 3：

**输入：**head = [1] 输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/

哈喽，大家好，今天给大家说一个经典题目，两两交换链表的节点，该题目要求，只能更改节点，不可以修改相关值。

此类题目可以使用三指针法来解决，需要交换的节点为 mid 和 pre，last 用来做标记位。

那么我们将这个题目拆解一下，主要有两个关键点

1. 如何做到 mid 和 pre 交换节点
2. mid 和 pre 交换节点之后，如何移动各指针，以完成下一轮的交换

下面我们来解析一下下图

第 1 步：mid 指向头节点，pre 指向 mid->next , 创建虚拟节点，last->next = mid

第 2 步：此时需要两两交换节点，也就是我们上面提到的关键点 1，last -> next = pre, mid -> next = pre -> next; pre->next = mid;这里有个细节需要注意，我们需要先执行mid -> next = pre -> next; 再执行pre->next = mid;，否则链表会被截断，无法进一步遍历

第 3 步：这一步，则是第二步的精简画法，没什么玄机

第 4 步：到了我们刚才提到的关键点 2，我们需要移动指针，方便进一步交换节点，首先我们移动 last 指针，到其新位置，则 last = mid;

第 5 步：此时我们需要执行 mid ，使其到新位置，但是这里我们需要注意的一点，假设 mid -> next == nullptr; 则说明，mid 指向的为链表的最后一个节点，则需要跳出循环，若 mid -> next != nullptr 则执行 mid = mid -> next; 将其移动到新位置

第 6 步：这需要将 pre 移动到新位置，则 pre = mid->next; 即可

以上 第 2 步对应关键点 1，第 4，5，6 步对应关键点 2，这样我们就将这个题目解决啦。

暂时无法在飞书文档外展示此内容

这样我们就解决了这个题目啦

详细代码如下

C++：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* mid = head;
        ListNode* pre = head->next;
        ListNode dummy(-1);
        dummy.next = mid;
        ListNode* newhead = &dummy;

        while (pre != nullptr) {
            newhead->next = pre;
            mid->next = pre->next;
            pre->next = mid;
            newhead = mid;
            if (mid->next == nullptr) {
                break;
            }
            mid = mid->next;
            pre = mid->next;
        }
        return dummy.next;
    }
};

题目视频版本

算法题讲解