24. 两两交换链表中的节点
题目描述
输入链表的头节点 head，链表用数组表示。
从头开始，把第 1、2 个节点互换位置，第 3、4 个节点互换位置，依此类推。节点数为奇数时，最后一个节点留在原处。
必须真正调整节点之间的连接，不能只改节点里的值。返回交换后链表的头节点，空链表返回 null。
示例 1
输入：head = [1,2,3,4] 输出：[2,1,4,3]
解释：1,2 互换，3,4 互换。
示例 2
输入：head = [] 输出：null
解释：空链表无需处理。
示例 3
输入：head = [1] 输出：[1]
解释：只有一个节点，没有可以交换的对象。
示例 4
输入：head = [1,2,3] 输出：[2,1,3]
解释：1,2 互换，剩下的 3 保持不动。
数据范围
- 节点数在
[0, 100]之间 0 <= Node.val <= 100
解题思路：哑节点迭代
prev 位于待交换一对之前，先保存 a、b，再重连三个 next。
为什么正确
prev 之前的节点均完成交换；prev.next 是未处理部分的头。
复杂度分析
时间 O(n)，额外空间 O(1)。
易错点
重连前保留 b 及后续链接，避免丢链或成环。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def swapPairs(self, head):
dummy = ListNode(0, head)
prev = dummy
while prev.next and prev.next.next:
a = prev.next
b = a.next
a.next = b.next
b.next = a
prev.next = b
prev = a
return dummy.nextclass Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode a = prev.next;
ListNode b = a.next;
a.next = b.next;
b.next = a;
prev.next = b;
prev = a;
}
return dummy.next;
}
}class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0, head);
ListNode* prev = dummy;
while (prev->next && prev->next->next) {
ListNode* a = prev->next;
ListNode* b = a->next;
a->next = b->next;
b->next = a;
prev->next = b;
prev = a;
}
return dummy->next;
}
};func swapPairs(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
prev := dummy
for prev.Next != nil && prev.Next.Next != nil {
a := prev.Next
b := a.Next
a.Next = b.Next
b.Next = a
prev.Next = b
prev = a
}
return dummy.Next
}var swapPairs = function(head) {
const dummy = new ListNode(0, head);
let prev = dummy;
while (prev.next && prev.next.next) {
const a = prev.next;
const b = a.next;
a.next = b.next;
b.next = a;
prev.next = b;
prev = a;
}
return dummy.next;
};function swapPairs(head: ListNode | null): ListNode | null {
const dummy = new ListNode(0, head);
let prev = dummy;
while (prev.next && prev.next.next) {
const a = prev.next;
const b = a.next;
a.next = b.next;
b.next = a;
prev.next = b;
prev = a;
}
return dummy.next;
}其他解法
两种方法都是 O(n) 时间；递归写法更直观，迭代写法省去递归栈，只用 O(1) 额外空间。
解法 2：递归 时间 O(n)，空间 O(n)
链表为空或只有一个节点时直接返回 head。否则记 newHead = head.next，先递归交换 newHead.next 开始的剩余链表，把结果接到 head.next。再令 newHead.next = head，返回 newHead。
只处理「前两个节点 + 剩余部分」，代码更短，不需要哑节点。递归深度为 n/2，占用 O(n) 栈空间，迭代版是 O(1)。
class Solution:
def swapPairs(self, head):
if head is None or head.next is None:
return head
new_head = head.next
head.next = self.swapPairs(new_head.next)
new_head.next = head
return new_headclass Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) return head;
ListNode* newHead = head->next;
head->next = swapPairs(newHead->next);
newHead->next = head;
return newHead;
}
};func swapPairs(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newHead := head.Next
head.Next = swapPairs(newHead.Next)
newHead.Next = head
return newHead
}var swapPairs = function(head) {
if (!head || !head.next) return head;
const newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
};function swapPairs(head: ListNode | null): ListNode | null {
if (!head || !head.next) return head;
const newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}