24、两两交换链表中的节点
24、两两交换链表中的节点
鲁迅曾说，不积跬步无以至千里，不积小流无以成江海。继续坚持刷题，每天进
步一天天，日积月累，就会发生质变。希望二哥的 LeetCode 题解越来越好，球
友们的算法水平也越来越高。
题意
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改
节点内部的值的情况下完成本题（即，只能进行节点交换）。
难度
中等
示例
024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E
4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9-20240206194202.png
输入：head = [1,2,3,4]
输出：[2,1,4,3]
分析 1
看到这道题，我们要先搞清楚什么是两两交换，比如 1->2->3->4，交换后就是 2->1->4-
>3。
第一个和第二个交换，第三个和第四个交换，以此类推。
我们可以用递归来解决这个问题，递归的终止条件是当前节点或者下一个节点为空，那么
递归的返回值就是当前节点。
比如说 1 和 2 交换后， 2 的 next 指向 1，1 的 next 指向下一次交换后的结果。
我们来看题解的代码：
class Solution {
public ListNode swapPairs(ListNode head) {
// 递归终止条件：链表没有节点或只有一个节点
if (head == null || head.next == null) {
return head;
}
// 准备交换
ListNode firstNode = head;
ListNode secondNode = head.next;
// 递归处理剩下的节点
firstNode.next = swapPairs(secondNode.next);
// 交换
secondNode.next = firstNode;
// 返回交换后新的头节点
return secondNode;
}
}
我们从链表的头节点 head 开始递归，每次处理一对节点，交换这对节点后，递归处理剩
下的节点。
如果链表没有节点或者只有一个节点，没有交换的需要，直接返回 head。看下面这幅图
就明白了。
024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E
4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9-20240206202128.png
来看题解效率：
024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E
4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9-20240206202549.png
分析 2
如果不想使用递归的话，我们也可以使用一个 while 循环来解决。
第一步，我们创建一个虚拟节点作为新链表的头节点，这可以简化边界条件的处理，虚拟
节点的下一个节点指向 head。
第二步，我们开始 while 循环，条件是 head 和 head.next 都不为空。
第三步，我们使用两个临时变量来保存 head 和 head.next，然后交换这两个节点。
第四步，记得更新指针。
第五步，返回虚拟节点的下一个节点。
我们来看下面的代码：
class Solution {
public ListNode swapPairs(ListNode head) {
// 创建哑节点
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode curr = prev.next; // 当前节点
ListNode next = curr.next; // 下一个节点
// 交换 curr 和 next
curr.next = next.next;
next.next = curr;
prev.next = next;
// 移动指针
prev = curr;
}
return dummy.next;
}
}
简单解释下：
• 创建一个虚拟节点 dummy，dummy 的 next 指向 head。
• 创建一个指针 prev，指向 dummy。
• 当 prev 的 next 和 next 的 next 都不为空时，进行交换。
• 交换后，prev 指向 curr，curr 指向 next，next 指向 curr 的 next。
• 返回 dummy 的 next。
024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E
4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9-20240206204539.png
因为增加了很多临时变量，所以代码没有递归简洁。
来看题解效率：
024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E
4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9-20240206204617.png
总结
其实有关链表的相关题目，最重要的切入角度，就是理清楚节点之间的关系，然后在纸上
画一画，不要一个劲的只靠脑子不靠笔，往往思考了很久的问题，动动笔，就会豁然开
朗，再用代码准确的描述出思路，这样子链表的问题便迎刃而解。
那这道题考察的还是链表的数据结构，以及递归和 while 循环的一些临时变量和边界条
件。
力扣链接：https://leetcode.cn/problems/swap-nodes-in-pairs/