两两交换链表中的节点

题目描述

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

示例

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

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

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

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

约束条件

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

我的解题过程

解题思路：迭代法

这道题的关键是理清楚交换两个节点时，指针需要怎么变化。

假设当前要交换的两个节点是 l1 和 l2，它们前面的节点是 tail，交换后的结构应该是：

交换前：tail -> l1 -> l2 -> next
交换后：tail -> l2 -> l1 -> next

需要修改三个指针：

1. tail.next = l2（tail 指向 l2）
2. l1.next = l2.next（l1 指向 l2 原来的下一个节点）
3. l2.next = l1（l2 指向 l1）

另外一个技巧是使用虚拟头节点（dummy node）。因为头节点也可能参与交换，使用虚拟头节点可以统一处理逻辑，不需要单独处理头节点的情况。

function swapPairs(head: ListNode | null): ListNode | null {
  let dummy = new ListNode(0, head);
  let tail = dummy;

  while (tail.next && tail.next.next) {
    let l1 = tail.next;
    let l2 = l1.next;

    // 执行交换
    tail.next = l2;
    l1.next = l2.next;
    l2.next = l1;

    // 移动到下一对的前一个位置
    tail = l1;
  }

  return dummy.next;
}

时间复杂度是 O(n)，只需要遍历一次链表。空间复杂度是 O(1)，只用了几个指针变量。

扩展思路：递归法

这道题也可以用递归来解决，思路更加简洁：

• 递归的终止条件：链表为空或只剩一个节点
• 递归的操作：交换前两个节点，然后递归处理剩下的链表

function swapPairs(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;

  let newHead = head.next;
  head.next = swapPairs(newHead.next);
  newHead.next = head;

  return newHead;
}

递归的时间复杂度也是 O(n)，但空间复杂度是 O(n)（递归调用栈的深度）。

小结

这道题是链表操作的经典题目，主要考察：

1. 指针操作：理清交换节点时各个指针的变化
2. 虚拟头节点：简化边界情况的处理
3. 迭代 vs 递归：两种思路都可以解决问题，各有优劣

链表题目的关键是画图！把交换前后的指针指向画出来，代码就容易写对了。