前言递归和链表是数据结构算法里两大高频考点。递归善于把大问题拆解为结构相同的子问题链表依靠指针完成节点连接。很多链表题目既可以用迭代循环实现也可以用递归优雅解决。本文结合基础概念 LeetCode 206反转链表、LeetCode24两两交换链表节点使用Python完整演示两种解法理清递归与链表指针操作的核心思维。一、递归基础概念什么是递归递归函数/过程调用自身。• 直接递归函数A直接调用A自己。• 间接递归A调用BB又调用A。• 尾递归递归调用是函数最后一条执行语句执行完递归调用后没有额外运算操作。递归模型分为两部分递归出口终止条件递归什么时候停下来给出明确结果防止无限递归栈溢出。递归体描述大问题和子问题之间的递推关系把原问题拆成规模更小的同类子问题。示例1阶乘递归数学定义\begin{cases}fun(1)1 \text{递归出口}\fun(n)n\times fun(n-1) \text{递归体}\end{cases}Python递归代码def fact(n):if n 1:return 1return n * fact(n-1)print(fact(5)) #输出120这是直接递归注意return n * fact(n‑1)递归调用之后还要做乘法不属于尾递归。真正尾递归要求return直接返回递归调用结果不再做计算。示例2斐波那契数列兔子问题规则F(0)0F(1)1n≥2时F(n)F(n‑1)F(n‑2)。def fib(n):if n 0:return 0if n 1:return 1return fib(n-1)fib(n-2)for i in range(7):print(fib(i),end ) #0 1 1 2 3 5 8递归会产生大量重复计算递归树可以看到大量重复节点大数据场景效率差适合理解递归思想实际开发优先迭代。什么时候适合用递归定义本身就是递归阶乘、斐波那契。数据结构是递归的单链表、树。链表 头节点 剩下的子链表天然适配递归思维。求解方法是递归分治、回溯类算法。二、单链表基础回顾单链表节点定义Pythonclass ListNode:definit(self, val0, nextNone):self.val valself.next next• val存储节点数据next保存下一个节点的引用。• 链表操作最容易踩坑修改指针前必须临时保存后继节点防止链表断链丢失后续数据。三、LeetCode 206 反转链表题目给单链表头节点head反转链表返回反转之后新头节点。例1→2→3→4→5 →5→4→3→2→1。解法1迭代双指针面试首选空间O(1)思路cur指向当前节点pre初始为None。循环中先用temp保存cur.next防止断链。cur.next pre完成当前节点反转。pre、cur向后移动直到cur等于None。循环结束pre就是新链表头。from typing import Optionalclass Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:cur headpre Nonewhile cur:temp cur.next #保存后续链表不可省略cur.next pre #反转指针pre curcur tempreturn pre解法2递归版本递归出口链表为空或者只有一个节点直接返回head。递归体先反转后面子链表再调整当前节点指针。class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:#递归出口if head is None or head.next is None:return headnew_head self.reverseList(head.next)head.next.next head #子链表尾部指向当前节点head.next None #断开旧指向防止循环return new_head递归是先一路递归走到链表末尾回溯的时候反转指针。空间复杂度O(n)占用函数调用栈。补充尾递归写法把pre、cur作为递归参数传入class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:def reverse(cur, pre):if cur is None:return pretemp cur.nextcur.next prereturn reverse(temp, cur)return reverse(head, None)四、LeetCode 24 两两交换链表中的节点题目描述给链表两两交换相邻节点返回新头节点。不能修改节点值只能交换节点指针。示例输入1‑2‑3‑4输出2‑1‑4‑3链表奇数长度最后一个节点保持不动。解法1迭代虚拟头节点dummy技巧虚拟头节点dummy不存有效数据指向head解决头节点参与交换需要特殊处理边界的麻烦。最后返回dummy.next。class Solution:def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]:dummy_head ListNode(nexthead)current dummy_head#必须同时存在下一个、下下个节点才能交换while current.next and current.next.next:temp current.next #第一个待交换节点temp1 current.next.next.next #保存交换之后的后续链表current.next current.next.next current.next.next temp temp.next temp1 current current.next.next #移动到下一组的前驱 return dummy_head.next解法2递归版本思路只处理当前前两个节点剩下交给递归处理。class Solution:def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]:#递归出口没有节点 或者只剩1个节点if head is None or head.next is None:return headnext_node head.nexthead.next self.swapPairs(next_node.next)next_node.next headreturn next_node五、总结对比题目 迭代 递归反转链表206 空间O(1)速度快面试优先写 空间O(n)栈开销代码简洁两两交换24 使用dummy虚拟头节点统一边界逻辑 递归逻辑简短适合理解分治思想递归做题记住两步写递归出口什么情况直接return不能再往下递归。相信递归递归函数可以正确处理规模更小的子问题本级只需要处理当前层逻辑。链表做题记住改动next之前一定要临时保存需要用到的节点引用避免断链丢失链表。