24. 两两交换链表中的节点 详细技术解析（两种解法）

24. 两两交换链表中的节点 详细技术解析两种解法本文针对LeetCode 24题「两两交换链表中的节点」展开详细解析从题目分析、核心思路、两种解题方法迭代法、递归法、代码实现到示例验证、常见错误规避逐步拆解链表交换的核心逻辑适用于算法面试、刷题进阶兼顾专业性与易懂性确保读者能掌握节点交换的核心技巧不修改节点内部值仅操作指针。一、问题描述给定一个单链表要求两两交换其中相邻的节点并返回交换后链表的头节点。核心约束必须在不修改节点内部的值的情况下完成本题即只能进行节点指针的操作不能直接修改 node.val。1.1 示例说明示例1输入head [1,2,3,4]输出[2,1,4,3]解析交换第1与第2个节点、第3与第4个节点指针重新连接不修改节点值。示例2输入head []输出[]解析空链表无需交换直接返回空。示例3输入head [1]输出[1]解析只有一个节点无相邻节点可交换直接返回原节点。1.2 提示信息链表中节点的数目在范围 [0, 100] 内0 ≤ Node.val ≤ 1001.3 核心难点本题的核心难点的是「指针的正确跳转」避免出现链表断裂或循环引用具体需注意两点交换相邻两个节点时需同时处理「前一个节点指向新的头」「两个节点内部指针交换」「交换后的尾指向后一个节点」三个步骤边界处理空链表、只有一个节点、链表长度为奇数最后一个节点不交换的场景。二、解题思路两种核心解法本题有两种常用解法迭代法推荐易理解、无递归栈开销和递归法代码简洁适合理解递归思想两种方法均严格遵循「不修改节点值仅操作指针」的约束。2.1 通用前提链表节点定义题目指定的链表节点定义如下代码必须严格遵循此格式# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next next2.2 解法一迭代法最优解2.2.1 核心思路迭代法的核心是「设置虚拟头节点遍历链表逐对交换相邻节点」步骤如下创建虚拟头节点dummy node指向原链表的头节点。虚拟头节点的作用是避免处理「头节点交换后新头节点不确定」的边界问题统一所有节点对的交换逻辑。设置两个指针prev、currprev 初始指向虚拟头节点curr 初始指向原头节点prev.next。遍历链表每次处理一对相邻节点curr 和 curr.next循环条件curr 不为空且 curr.next 不为空确保有两个节点可交换。交换步骤关键记为三步法暂存 curr.next记为 next_node避免交换时指针丢失curr.next 指向 next_node.next让当前节点跳过下一个节点指向更后面的节点next_node.next 指向 curr完成两个节点的交换prev.next 指向 next_node让前一个节点指向交换后的新头连接整个链表移动指针prev 移动到 curr交换后的尾节点curr 移动到 curr.next下一对节点的第一个节点进入下一次循环。遍历结束后返回虚拟头节点的 next交换后的新头节点。2.2.2 图解示意以示例1 [1,2,3,4] 为例初始状态dummy → 1 → 2 → 3 → 4prevdummycurr1第一次交换1和2next_node 2curr.next 31→3next_node.next 12→1prev.next 2dummy→2此时链表dummy → 2 → 1 → 3 → 4prev1curr3。第二次交换3和4next_node 4curr.next None3→Nonenext_node.next 34→3prev.next 41→4此时链表dummy → 2 → 1 → 4 → 3prev3currNone循环结束。最终返回 dummy.next 2即交换后的头节点。2.2.3 迭代法代码实现# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextclassSolution:defswapPairs(self,head:Optional[ListNode])-Optional[ListNode]:# 1. 创建虚拟头节点避免头节点交换的边界问题dummyListNode(0)dummy.nexthead# 2. 初始化指针prev指向虚拟头curr指向原头节点prevdummy currhead# 3. 遍历链表每次交换一对相邻节点curr和curr.next都存在时whilecurrandcurr.next:# 暂存下一个节点要和curr交换的节点next_nodecurr.next# 第一步curr跳过next_node指向next_node的下一个节点curr.nextnext_node.next# 第二步next_node指向curr完成两个节点的交换next_node.nextcurr# 第三步prev指向next_node连接前一段链表和交换后的节点prev.nextnext_node# 移动指针准备下一次交换prevcurr# prev移动到交换后的尾节点原currcurrcurr.next# curr移动到下一对的第一个节点# 4. 返回虚拟头节点的next即交换后的新头节点returndummy.next2.3 解法二递归法2.3.1 核心思路递归法的核心是「将大问题拆解为小问题」两两交换链表的相邻节点等价于「交换当前两个节点 递归交换剩下的链表」步骤如下递归终止条件当前节点为空空链表或当前节点的下一个节点为空只有一个节点无法交换直接返回当前节点。递归处理假设当前节点为 curr下一个节点为 next_node先递归交换 next_node.next 开始的链表得到交换后的子链表头节点。交换当前两个节点next_node.next 指向 currcurr.next 指向递归返回的子链表头节点连接交换后的子链表。返回 next_node当前交换后的头节点作为上一层递归的子链表头。关键理解递归的本质是「从链表末尾开始交换逐步向上回溯」无需手动维护指针移动代码更简洁但存在递归栈开销链表长度最大100递归深度最大50无栈溢出风险。2.3.2 递归法代码实现# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextclassSolution:defswapPairs(self,head:Optional[ListNode])-Optional[ListNode]:# 递归终止条件无节点或只有一个节点无需交换ifnotheadornothead.next:returnhead# 暂存当前节点的下一个节点要交换的节点next_nodehead.next# 递归交换剩下的链表从next_node.next开始得到子链表头head.nextself.swapPairs(next_node.next)# 交换当前两个节点next_node指向headnext_node.nexthead# 返回交换后的头节点next_node作为上一层的子链表头returnnext_node三、代码解析与复杂度分析3.1 迭代法解析与复杂度代码解析虚拟头节点 dummy统一所有节点对的交换逻辑避免单独处理头节点交换的边界如示例1中交换1和2后新头节点是2通过 dummy.next 直接获取。指针移动prev 和 curr 的移动的是关键每次交换后prev 移动到交换后的尾节点currcurr 移动到下一对的第一个节点确保遍历不遗漏、不重复。边界处理循环条件「curr and curr.next」确保只有两个及以上节点时才进行交换自然处理空链表、单个节点、奇数长度链表的场景。复杂度时间复杂度O(n)n 为链表节点数每个节点仅被遍历一次交换操作是常数时间。空间复杂度O(1)仅使用3个指针dummy、prev、curr无额外空间开销是最优解法。3.2 递归法解析与复杂度代码解析递归终止条件直接返回无法交换的节点避免递归无限循环。递归逻辑先处理后面的子链表再交换当前两个节点确保链表连接正确避免先交换当前节点导致后续链表指针丢失。简洁性代码仅需几行无需手动维护指针移动核心是利用递归栈保存后续链表的状态。复杂度时间复杂度O(n)每个节点仅被递归处理一次。空间复杂度O(n)递归栈的深度为 n/2最坏情况链表长度为偶数属于额外空间开销。3.3 两种解法对比解法时间复杂度空间复杂度优点缺点迭代法O(n)O(1)无栈开销效率高易理解适合工程实践代码稍长需手动维护指针递归法O(n)O(n)代码简洁逻辑清晰适合理解递归思想有递归栈开销链表过长可能栈溢出本题无风险四、示例验证两种解法均适用4.1 示例1head [1,2,3,4]迭代法如前文图解最终返回 [2,1,4,3]正确。递归法递归调用 swapPairs(3) → 3.next4递归 swapPairs(None) 返回 None4.next33.nextNone返回 4回到上层2.next41.next3返回 2最终返回 2链表为 [2,1,4,3]正确。4.2 示例2head []迭代法currheadNone循环不执行返回 dummy.nextNone正确。递归法headNone直接返回 None正确。4.3 示例3head [1]迭代法curr1curr.nextNone循环不执行返回 dummy.next1正确。递归法head.nextNone直接返回 1正确。4.4 扩展示例head [1,2,3]输入[1,2,3]输出[2,1,3]解析仅交换前两个节点第三个节点不交换两种解法均能正确处理验证了奇数长度链表的边界。五、常见错误与注意事项5.1 常见错误点错误1修改节点内部值违反题目约束。例如直接交换 curr.val 和 curr.next.val虽然能得到正确结果但不符合「只能进行节点交换」的要求面试中会被判错误。错误2指针跳转顺序错误导致链表断裂。例如先执行 next_node.next curr再执行 curr.next next_node.next此时 curr.next 会指向 curr循环引用链表断裂。错误3未处理边界场景导致空指针异常。例如未判断 curr.next 是否为空直接访问 curr.next.next当链表长度为奇数时会出现空指针。错误4递归法中未正确连接子链表。例如递归后未将 curr.next 指向递归返回的子链表头导致链表断裂。5.2 注意事项迭代法优先使用工程实践中迭代法无栈开销效率更高且不易出现栈溢出问题是首选解法。虚拟头节点的作用务必使用虚拟头节点简化头节点交换的边界处理避免单独判断头节点。指针暂存交换节点时务必暂存需要用到的指针如 next_node避免指针丢失导致链表断裂。递归深度递归法适合链表长度较小的场景本题链表长度最大100递归深度最大50无栈溢出风险若链表长度极大优先使用迭代法。六、总结本题的核心是「链表指针的精准操作」两种解法各有优势迭代法高效、无额外空间适合工程实践递归法简洁、逻辑清晰适合理解递归思想。解题关键在于严格遵循「不修改节点值仅操作指针」的约束掌握迭代法的「虚拟头节点 三步交换 指针移动」逻辑或递归法的「终止条件 子问题拆解」逻辑重视边界处理覆盖空链表、单个节点、奇数长度链表等场景。本题是链表操作的经典题型考察的核心是对链表指针的掌控能力掌握本题后可快速迁移到「k个一组翻转链表」等更复杂的链表操作问题为后续算法学习奠定基础。