hot100 两两交换链表中的节点(24)

本题采用双指针局部翻转算法又称“K个一组翻转链表的特化变体”结合哑节点哨兵设计解决单链表相邻节点两两交换的问题。其核心本质是将链表划分为若干个长度为 2 的独立子区间在不改变节点内部数值的前提下利用三指针局部逆序拓扑结构进行原地指针重定向并通过外部边界指针重新拼接。当前提供的源码实现了在时间复杂度 O(N) 和额外空间复杂度 O(1) 条件下的全局最优原地修改最终走向是高效安全地完成节点重组并返回交换后的新链表头。一、 问题本质与数据模型对于由ListNode构成的单链表题目要求在不改变节点内部val的前提下两两互换相邻节点的相对位置。若直接操作头节点会导致原本的指针指向发生逻辑断层例如 1-2 变成 2-1 后原链表外部指向 1 的指针需要改为指向 2。为了消除首组节点交换与其他内部节点交换的控制流差异算法引入了以下模型“哑节点Dummy Node定位模型”在head节点之前挂载一个虚拟的dummy节点。这使得任何一组待交换的两个节点在物理上都必然拥有一个统一的“前驱节点p0”从而将全流程的指针重定向操作归一化。“长度驱动的局部翻转滑窗”算法先通过单次线性扫描统计链表总长度动态维护一个计数器。当剩余未处理节点数大于或等于 2 时滑窗继续向右平移。在窗口内部利用微观的链表逆序控制流将两个节点的 next 指针进行对调。二、 算法演进对比在解决两两交换链表节点的问题时基于迭代的局部翻转法在时空效率上具备绝对的确定性解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷节点数值交换法O(N)O(1)不改变拓扑结构直接利用临时变量交换相邻节点的val数值违反了题目“不得修改节点内部值”的严格约束属于非法解法递归模拟法O(N)O(N)每次递归处理两个节点将当前组的尾节点指向下一组递归的返回值递归调用会在系统栈中产生深度为 N/2 的栈帧开销无法实现常数阶空间的资源约束局部翻转迭代法当前解法O(N)O(1)统计长度后利用三指针在局部执行 2 个节点的标准反转随后通过 p0 轴心重组边界控制变量较多需要严密计算子区间反转后与前后断点的桥接关系三、 核心分支控制逻辑与决策证明当前源码的控制流由一个长度统计循环与一个while (count 2)的拓扑翻转控制网串联而成其内部决策及边界缝合证明如下1. 动态步长控制器while (count 2)决策证明两两交换的前提是当前滑窗内必须存在至少 2 个有效节点。如果链表节点总数为奇数最后剩余的单个节点不满足交换条件。结论以count 2作为外层状态机的推进边界可以自适应地在节点不足时提前终止循环保障了奇数长度链表尾部节点的物理稳定性。2. 内部标准反转拓扑for (int i 0; i 2; i)执行在 2 次迭代中执行标准的链表反转nxt cur.next; cur.next pre; pre cur; cur nxt;。数学证明进入循环前pre nullcur指向当前对的首节点例如节点 1。第一次迭代后节点 1 的next变成null暂时的pre移到节点 1cur移到节点 2。第二次迭代后节点 2 的next变成节点 1pre移到节点 2cur移到节点 3。结论内部循环结束后局部子区间的方向完全逆序pre正好指向原对子的尾节点现新头部cur正好指向下一对子的起始节点断点处的后继。3. 三点边界缝合反转后的外组挂载执行Javap0.next.next cur; // 缝合后半段边界 p0.next pre; // 缝合前半段边界 p0 nextP0; // 步进控制指针决策证明反转前p0.next记录的是原对子的首节点反转后的尾节点。执行p0.next.next cur让反转后的尾节点无缝挂载到后续未处理的断点cur上执行p0.next pre让前驱节点指向反转后的新头节点pre。结论三步挂载完成了局部逆序段与主链的前后物理拼合实现了原地重组。四、 算法执行状态机步进示例以输入链表head [1, 2, 3, 4]为例总长度count 4初始p0指向dummy第一轮循环的步进演进过程如下表所示关键节点状态指针/变量当前定位拓扑微观指向变化执行的控制动作链表局部拓扑状态说明进入外循环count4, p0dummydummy - 1 - 2 - 3 - 4记录nextP0 1初始化prenull,cur1准备对第一组[1, 2]执行局部翻转内循环 i0pre1, cur21 - null节点 1 斩断前向引用暂指向 null节点 1 单独剥离内循环 i1pre2, cur32 - 1 - null节点 2 的 next 重定向指向节点 1[1, 2]内部反转完成形如2 - 1缝合动作 1p0.next.next cur1 - 3将反转后的尾部节点 1指向后继断点节点 3链表变为dummy-1-3-4和2-1-3缝合动作 2p0.next predummy - 2将前驱dummy指向反转后的新头部节点 2链表拼接成功dummy - 2 - 1 - 3 - 4滑窗步进p0 nextP0p0 移动到节点 1将p0轴心平移至节点 1count减 2 变为 2第一轮收敛p0准确就位准备处理[3, 4]五、 源码实现/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode swapPairs(ListNode head) { // 步骤 1线性扫描链表统计节点总长度 ListNode curr head; int count 0; while (curr ! null) { curr curr.next; count; } // 步骤 2引入虚拟哑节点 dummy固化首组节点交换的前驱边界 ListNode dummy new ListNode(0, head); // 初始化全局控制轴心指针 p0 指向哑节点 ListNode p0 dummy; // 步骤 3滑窗迭代只要剩余节点数大于或等于 2持续执行成对反转 while (count 2) { count - 2; // 消费当前滑窗内的 2 个节点 ListNode nextP0 p0.next; // 提前暂存下一轮交换所需的 p0 轴心位置即原对子的首节点 ListNode cur p0.next; // 初始化局部反转的工作指针 cur ListNode pre null; // 初始化局部反转的前驱指针 pre // 内层循环通过 2 次指针重定向将当前组内的 2 个节点执行标准就地反转 for (int i 0; i 2; i) { ListNode nxt cur.next; // 暂存后继探针 cur.next pre; // 核心逆序将当前节点的 next 指向前驱 pre cur; // pre 指针平移 cur nxt; // cur 指针平移 } // 步骤 4三点边界缝合恢复子区间与主链的前后拓扑关联 p0.next.next cur; // 将原首节点反转后的尾节点的 next 指向未处理的后继断点 cur p0.next pre; // 将前驱 p0 的 next 指向新生成的头节点 pre // 移动轴心指针平移滑窗至下一组的前驱位置 p0 nextP0; } // 返回剥离哨兵后的真实链表新头节点 return dummy.next; } }六、 复杂度分析1. 时间复杂度O(N)分析第一阶段长度统计curr指针自头至尾平滑移动对链表执行了一次完整的线性扫描耗时为 N 次步进。第二阶段成对翻转外层while循环总共执行 N/2 次。在每次迭代内部固定的for循环精确执行 2 次指针重定向操作。因此节点被访问和修改的次数依然与 N 呈线性关系。结论全流程的时间损耗与链表中的总节点数 N 呈严格的线性正比关系。2. 空间复杂度O(1)分析算法在执行期间除了实例化了一个用于边界防护的哨兵哑节点dummy之外仅在系统栈内存中分配了curr、p0、nextP0、cur、pre、nxt等基础类型的局部引用指针。所有链表的重组和交换均是在原节点上修改指针指向完成的原地In-place操作。结论没有任何依赖于输入数据规模的外部动态内存扩张空间损耗恒定为常数阶。