链表-两两交换（Java的三种解法）

道题是链表操作的一个经典问题，掌握了它，你对链表的指针操作和递归思维会有更深的理解。只要你跟着我的思路走一遍，自己动手写写代码，很快就能独立解决这类问题！咱们现在就来聊聊这道题吧

1. 看到这道题目时我想到了什么，以及如何运用现实案例讲解

你有没有想过，生活中很多事情都像是“交换顺序”或者“重新排列”。比如说，你在排队买东西，队伍里的人两两交换位置，前面的人变成后面，后面的人变成前面，这就是一种“两两交换”的操作。

再举个贴近算法的例子：想象你在整理一排书，原本是按顺序摆放的，但你想把相邻的两本书交换位置，比如第1本和第2本换，第3本和第4本换，这样整个书架的顺序就变了。这就像链表的两两交换，我们需要调整指针，让相邻节点的位置互换。

业务场景：这道题在实际业务中有很多应用，比如：

• 数据排序：在某些场景下，需要对数据进行局部重排，比如用户列表中两两交换显示顺序，用于A/B测试。
• 任务调度：在任务队列中，调整任务执行顺序，比如优先级相邻任务交换，提升调度效率。
• 游戏设计：在游戏排行榜中，动态调整玩家位置，比如相邻玩家交换，用于视觉效果或平衡机制。

2. 解法分析：至少3种解法，最优解法和最快解法

解法1：递归（Recursion）——直观且代码简洁

思路：用递归的方式处理链表的两两交换。每次处理当前节点和下一个节点，交换它们的位置，然后递归处理剩余的链表。终止条件是当前节点为空或下一个节点为空。

• 时间复杂度：O(n)，n是链表节点数量，每个节点只处理一次。
• 空间复杂度：O(n)，由于递归调用栈，最坏情况下为链表长度。

解法2：迭代（Iteration with Dummy Node）——更符合工程实践

思路：用迭代的方式处理链表，引入一个哑节点（dummy node）作为辅助，方便处理头节点交换。每次处理一对节点，调整指针完成交换，然后移动到下一对节点。

• 时间复杂度：O(n)，每个节点只遍历一次。
• 空间复杂度：O(1)，只用常数级额外空间。

解法3：迭代（Iteration without Dummy Node）——直接操作头节点

思路：与解法2类似，但不引入哑节点，直接操作头节点。需要额外处理头节点交换的情况，代码逻辑稍复杂，但也能实现两两交换。

• 时间复杂度：O(n)，每个节点只遍历一次。
• 空间复杂度：O(1)，只用常数级额外空间。

最优解法和最快解法

• 最优解法：如果追求代码可读性和工程实践，推荐迭代解法（带哑节点），因为它空间复杂度低，逻辑清晰，容易维护。如果是初学者或面试中追求简洁，递归解法也是不错的选择。
• 最快解法：在实际运行中，**迭代解法（带哑节点）**通常是最快的，因为它避免了递归的调用栈开销，且指针操作效率高。

迭代解法（带哑节点）模板（Java）：

publicListNodeswapPairs(ListNode head){ if(head ==null|| head.next ==null)return head;ListNode dummy =newListNode(0); dummy.next