跳到主要内容

LeetCode 24. 两两交换链表中的节点

本节目标

借助哨兵节点统一重连相邻节点对，并保留不足一对的尾节点。

查看 LeetCode 原题

题意与边界​

每两个相邻节点交换位置并返回新链表头。只能改变节点之间的连接，不能交换节点值；空链表、单节点以及奇数长度链表最后不足一对的节点都保持原样。

哨兵节点下的局部重连​

prev 始终指向下一对节点之前的位置。设这一对为 first、second，依次让 first 接到第二个节点之后、second 接到 first、prev 接到 second，然后把 prev 推进到已经交换后的 first。

正确性依据​

每轮开始时，prev 之前的所有节点已经按对交换并正确连好，prev.next 是尚未处理部分的第一个节点。三次重连只改变当前一对的相对顺序并保留后继入口，随后不变量推进到下一对。循环退出时剩余节点不足两个，按要求保持原顺序。

代码实现​

C++17
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0, head);
        ListNode* prev = &dummy;
        while (prev->next != nullptr && prev->next->next != nullptr) {
            ListNode* first = prev->next;
            ListNode* second = first->next;
            first->next = second->next;
            second->next = first;
            prev->next = second;
            prev = first;
        }
        return dummy.next;
    }
};

复杂度分析​

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。

易错点​

  • 交换节点值而不是节点本身。
  • 重连顺序错误，先覆盖了仍需使用的后继指针。
  • 忘记哨兵节点，导致头节点这一对需要额外分支。

模式迁移​

哨兵节点把“修改链表头”转化为普通的前驱重连。删除、分组翻转和局部归并中，只要头部可能变化，都可以先建立稳定前驱。