图解两两交换链表节点｜虚拟头节点与四指针法高效实现
本文以LeetCode经典链表操作为例，深入讲解如何通过虚拟头节点与四指针法实现时间复杂度O(n)的高效节点交换，详解边界处理与指针操作技巧。
1. 题目链接
LeetCode 24. 两两交换链表中的节点
2. 题目描述
给定一个链表，两两交换相邻节点，要求不能修改节点内部值，仅通过修改指针完成操作。若链表长度为奇数，最后一个节点保持原位。
示例说明
输入：head = [1,2,3,4]
输出：[2,1,4,3]
解释：第一组交换1↔2，第二组交换3↔4
输入：head = [5]
输出：[5]
解释：单个节点无需处理
3. 示例分析
示例1：偶数长度链表
原始链表：
Dummy→1→2→3→4→∅（Dummy为虚拟头节点）
第一轮交换：
Dummy→2→1→3→4→∅
指针移动后：
Dummy→2→1→3→4→∅
第二轮交换：
Dummy→2→1→4→3→∅
示例2：奇数长度链表
原始链表：
Dummy→A→B→C→∅
处理过程：
- 交换A↔B →
Dummy→B→A→C→∅ - C无后续节点，终止操作
4. 算法思路
核心：四指针联动法
- 虚拟头节点：避免处理头节点特殊逻辑
- 四指针体系：
prev：当前组前驱节点cur：当前待交换首节点next：当前待交换次节点nnext：下一组的首节点
- 三步交换法：
Step1: prev → next Step2: next → cur Step3: cur → nnext
执行流程图示
初始状态： [prev]→[cur]→[next]→[nnext]
执行交换： [prev]→[next]→[cur]→[nnext]
移动指针： prev → cur → ...
5. 边界条件与注意事项
关键边界处理
- 空链表或单节点链表：直接返回原链表
- 奇数长度链表：最后一节点不处理
- 指针越界防护：
if(cur) next = cur->next; // 检查next是否存在 if(next) nnext = next->next; // 检查nnext是否存在
易错点警示
- 指针更新顺序错误：必须先修改
prev->next再移动指针 - 内存泄漏风险：虚拟头节点必须显式释放
- 循环条件设计：
while(cur && next) // 必须同时存在两个待交换节点
6. 代码实现
class Solution {
public:ListNode* swapPairs(ListNode* head) {if (!head || !head->next) return head;// 创建虚拟头节点ListNode* newhead = new ListNode(0);newhead->next = head;// 初始化四指针体系ListNode *prev = newhead, *cur = prev->next;ListNode *next = cur->next, *nnext = next->next;while (cur && next) { // 存在可交换节点对// Step1: 前驱节点链接次节点prev->next = next; // Step2: 次节点逆指回首节点next->next = cur; // Step3: 首节点链接后续节点cur->next = nnext; // 移动指针准备下一组交换prev = cur; // 前驱移至当前组末尾cur = nnext; // 当前节点移至下一组next = cur ? cur->next : nullptr; // 安全获取nextnnext = next ? next->next : nullptr; // 安全获取nnext}ListNode* res = newhead->next;delete newhead; // 释放虚拟头节点return res;}
};
总结
本算法通过虚拟头节点与四指针体系，以O(n)时间复杂度和O(1)空间复杂度高效完成节点交换。关键点在于：1）利用prev维护链表连续性；2）严格把控指针移动顺序；3）安全防护指针越界。掌握该解法后，可轻松应对各类链表变形操作题目，如K个一组翻转链表等进阶题型。