010-两两交换链表中节点（哑节点）

两两交换链表中的节点

问题描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

注意：不能只是单纯改变节点内部的值，而是需要实际进行节点交换。

示例

输入：1->2->3->4
输出：2->1->4->3

解决思路

方法：迭代法

1. 使用一个哑节点(dummy node)作为链表的起始点
2. 维护三个指针：
   • prev：指向当前要交换的两个节点的前一个节点
   • first：指向要交换的第一个节点
   • second：指向要交换的第二个节点
3. 每次交换两个节点，并更新指针位置

算法步骤

1. 创建哑节点，指向链表头部
2. 初始化prev指针指向哑节点
3. 当prev.next和prev.next.next都存在时：
   • 设置first和second指针
   • 执行交换操作
   • 移动prev指针到下一组的前面

JavaScript实现

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

function swapPairs(head) {
    // 创建哑节点
    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    
    while (prev.next !== null && prev.next.next !== null) {
        // 初始化要交换的两个节点
        const first = prev.next;
        const second = prev.next.next;
        
        // 执行交换
        first.next = second.next;
        second.next = first;
        prev.next = second;
        
        // 移动prev指针
        prev = first;
    }
    
    return dummy.next;
}

复杂度分析

• 时间复杂度：O(n)，需要遍历整个链表一次
• 空间复杂度：O(1)，只使用了常数个额外空间

递归解法

function swapPairs(head) {
    // 递归终止条件
    if (head === null || head.next === null) {
        return head;
    }
    
    // 要交换的两个节点
    const first = head;
    const second = head.next;
    
    // 递归交换后面的节点
    first.next = swapPairs(second.next);
    second.next = first;
    
    // 返回新的头节点
    return second;
}

边界情况考虑

1. 空链表：直接返回null
2. 单节点链表：直接返回该节点
3. 奇数长度链表：最后一个节点不交换

问题形象化理解

想象你有一串珍珠项链，每颗珍珠上有一个数字。现在要求你把相邻的两颗珍珠交换位置：

原项链：①→②→③→④→⑤
交换后：②→①→④→③→⑤

为什么需要哑节点？

哑节点（dummy node）就像一个”临时挂架”，帮助我们统一处理头节点的交换：

加入哑节点后：
哑→①→②→③→④→⑤

这样我们就不需要特殊处理头节点了，所有节点交换都可以用相同的方式处理。

详细步骤拆解（以 1→2→3→4 为例）

初始状态

哑→①→②→③→④→null
↑
prev

第一次交换（交换①和②）

1. 确定要交换的节点：

   • first = prev.next = ①
   • second = prev.next.next = ②

2. 执行交换：

   • ①.next = ②.next → ①.next = ③
   • ②.next = ①
   • prev.next = ②

3. 交换后状态：

   哑→②→①→③→④→null
   ↑
   prev

第二次交换（交换③和④）

1. 移动prev指针：prev = ①

2. 确定要交换的节点：

   • first = ①.next = ③
   • second = ①.next.next = ④

3. 执行交换：

   • ③.next = ④.next → ③.next = null
   • ④.next = ③
   • ①.next = ④

4. 交换后状态：

   哑→②→①→④→③→null
   ↑
   prev

终止条件

当prev.next或prev.next.next为null时停止（没有足够的节点可以交换了）

指针变化图解

初始：
dummy → ① → ② → ③ → ④ → null
 ↑prev   ↑f   ↑s

第一次交换后：
dummy → ② → ① → ③ → ④ → null
             ↑prev ↑f   ↑s

第二次交换后：
dummy → ② → ① → ④ → ③ → null
                         ↑prev

代码逐行解释

function swapPairs(head) {
    const dummy = new ListNode(0); // 创建哑节点
    dummy.next = head;            // 哑节点指向原链表头
    let prev = dummy;             // prev初始指向哑节点
    
    // 当还有至少两个节点可以交换时
    while (prev.next && prev.next.next) {
        const first = prev.next;      // 第一个要交换的节点
        const second = prev.next.next; // 第二个要交换的节点
        
        // 执行交换
        first.next = second.next; // ①指向③
        second.next = first;      // ②指向①
        prev.next = second;       // prev指向②
        
        prev = first; // 移动prev到下一组的前面（现在是①）
    }
    
    return dummy.next; // 返回新链表的头
}

常见误区

1. 忘记更新prev指针：会导致无限循环
2. 交换顺序错误：必须先保存second.next，再改变second.next
3. 边界条件处理：空链表或单节点链表直接返回

生活化类比

想象你在帮小朋友排队：

• 每次让相邻的两个小朋友交换位置
• 你站在前一对小朋友后面（prev指针）
• 指挥前面两个小朋友（first和second）换位置
• 然后你走到刚刚换完的那对小朋友后面
• 重复这个过程直到队尾

递归解法理解

function swapPairs(head) {
    // 递归终止条件：没有节点或只有一个节点
    if (!head || !head.next) return head;
    
    // 要交换的两个节点
    const first = head;
    const second = head.next;
    
    // first指向后面已经交换好的链表
    first.next = swapPairs(second.next);
    // second指向first完成交换
    second.next = first;
    
    // 返回新的头节点
    return second;
}

递归过程：

1. 先递归到链表末尾
2. 从后往前两两交换
3. 每次返回交换后的子链表头

复杂度分析

• 时间复杂度：O(n)，每个节点只被访问一次
• 空间复杂度：
  • 迭代法：O(1)
  • 递归法：O(n)（递归调用栈）

总结

两两交换链表节点的关键：

1. 使用哑节点简化头节点处理
2. 维护三个关键指针：prev、first、second
3. 按照固定顺序执行指针修改
4. 每次交换后正确移动prev指针

通过这种逐步交换的方式，我们可以高效地完成链表节点的两两交换。