Skip to main content

两两交换链表中的节点

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

示例 1： image

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

输入：head = [] 输出：[] 示例 3：

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

方法思路​

  1. 使用虚拟头节点：简化边界处理，避免单独处理头节点。
  2. 三指针法：维护三个指针 prev、curr、next，分别指向当前处理的两个节点的前一个节点、第一个节点和第二个节点。
  3. 交换逻辑：
    • 将 prev 的 next 指向 next；
    • 将 curr 的 next 指向 next 的下一个节点；
    • 将 next 的 next 指向 curr。
  4. 指针移动：交换完成后，将 prev 移动到 curr，curr 移动到其新的 next，继续处理后续节点。

代码实现​

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function swapPairs(head) {
    const dummy = new ListNode(0); // 虚拟头节点
    dummy.next = head;
    let prev = dummy;
    
    while (prev.next && prev.next.next) {
        const curr = prev.next;
        const next = curr.next;
        
        // 交换节点
        prev.next = next;
        curr.next = next.next;
        next.next = curr;
        
        // 移动prev指针到下一组的前一个节点
        prev = curr;
    }
    
    return dummy.next;
}

复杂度分析​

  • 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历每个节点一次。
  • 空间复杂度：O(1)，只需要常数级的额外空间。

示例验证​

输入：链表 1 → 2 → 3 → 4
输出：链表 2 → 1 → 4 → 3

过程：

  1. 初始状态：
    dummy → 1 → 2 → 3 → 4
    prev 指向 dummy，curr 指向 1，next 指向 2。

  2. 第一次交换：

    • prev.next = next：dummy → 2
    • curr.next = next.next：1 → 3
    • next.next = curr：2 → 1
      链表变为：dummy → 2 → 1 → 3 → 4
      prev 移动到 1，curr 指向 3，next 指向 4。

  3. 第二次交换：

    • prev.next = next：1 → 4
    • curr.next = next.next：3 → null
    • next.next = curr：4 → 3
      链表变为：dummy → 2 → 1 → 4 → 3 → null
      prev 移动到 3，curr 和 next 均为 null，结束循环。

关键细节说明​

  1. 虚拟头节点的作用：确保所有交换操作都遵循统一逻辑，无需特殊处理头节点。
  2. 循环条件：prev.next && prev.next.next 确保每次处理时都有两个节点可供交换。
  3. 指针移动顺序：交换后，prev 必须移动到当前处理的第二个节点（即 curr），而非直接跳到下一组的前一个节点，否则会导致链表断裂。

该方法通过一次遍历完成所有相邻节点的交换，高效且直观，是处理链表交换问题的标准解法。