递归与链表：从基础到LeetCode实战

一、前言在数据结构与算法的学习过程中递归和链表是两个绕不开的重要概念。递归是一种优雅的编程思想而链表则是数据结构的基础之一。当两者相遇往往能碰撞出精妙的解法。本文将从递归的基本概念出发结合链表这一数据结构详细讲解LeetCode上的两道经典题目——206. 反转链表和24. 两两交换链表中的节点帮助大家建立起递归解题的思维框架。所有示例代码均使用 Python 实现。二、递归概述2.1 什么是递归递归简单来说就是在定义一个过程或函数时出现调用本过程或本函数的情况。用一句经典的故事来理解从前有座山山中有座庙庙里有个老和尚老和尚在给小和尚讲故事“从前有座山山中有座庙庙里有个老和尚老和尚在给小和尚讲故事……”递归根据调用方式可以分为两类直接递归函数直接调用自身间接递归函数p调用函数q而q又调用p如果一个递归函数中递归调用语句是最后一条执行语句则称为尾递归。2.2 递归模型一个完整的递归模型由两部分组成递归出口确定递归何时结束即终止条件递归体确定递归求解时的递推关系以经典的阶乘函数 n! 为例pythondef factorial(n):if n 1: # 递归出口return 1return n * factorial(n-1) # 递归体其递归模型可抽象为textfactorial(1) 1 // 递归出口factorial(n) n * factorial(n-1) // 递归体2.3 斐波那契数列斐波那契数列是递归的经典应用场景。这个数列从第3项开始每一项都等于前两项之和01123581321345589……其数学定义为textF(0) 0F(1) 1F(n) F(n-1) F(n-2) (n ≥ 2)用Python实现如下pythondef fibonacci5(n):def fn(i):if i 1:return 1if i 0:return 0else:return fn(i-2) fn(i-1)for i in range(n):print(fn(i))2.4 什么时候用递归以下三种情况常常会用到递归定义是递归的如斐波那契数列数据结构是递归的如链表、树问题的求解方法是递归的如分治算法三、链表基础知识在正式解题之前我们先回顾一下链表的基本概念。链表是一种通过指针将一组零散的内存块串联起来的线性数据结构。与数组不同链表不要求存储在一块连续的内存中因此对内存的要求更低但随机访问的性能不如数组。单链表的每个节点包含两部分数据域val 存储数据指针域next 指向下一个节点Python 中的链表节点定义pythonclass ListNode:definit(self, val0, nextNone):self.val valself.next next可以用一个形象的比喻来理解链表就像一列火车每节车厢就是一个节点车厢之间相互连接。四、LeetCode 206. 反转链表4.1 题目描述给你单链表的头节点 head 请你反转链表并返回反转后的链表。示例输入head [1,2,3,4,5]输出[5,4,3,2,1]4.2 方法一迭代法双指针迭代法是反转链表最直观的解法核心思想是逐个改变节点的指向。思路图解定义 cur 指针指向头节点pre 指针指向 None遍历链表每次将 cur.next 用 tmp 保存防止丢失将 cur.next 指向 pre完成当前节点的反转移动 pre 和 cur 指针继续处理下一个节点当 cur 指向 None 时循环结束pre 即为新链表的头节点代码实现Python pythondef reverseList(head):cur headpre Nonewhile cur:tmp cur.next # 保存下一个节点cur.next pre # 反转指向pre cur # pre 前移cur tmp # cur 前移return pre复杂度分析时间复杂度O(n)只需遍历一次链表空间复杂度O(1)只使用了常数个指针4.3 方法二递归法递归法同样可以实现链表反转其思路与迭代法类似但用递归的方式来实现指针的移动。代码实现Python pythondef reverse(pre, cur):if cur is None:return pretmp cur.nextcur.next prereturn reverse(cur, tmp)def reverseList(head):return reverse(None, head)递归思路reverse(pre, cur) 函数的意义是反转以 cur 为头、pre 为前驱的链表返回反转后的新头节点。递归的终止条件是 cur None此时 pre 就是新链表的头节点。此外也可以使用更简洁的单函数递归后序遍历版本pythondef reverseList(head):# 递归终止条件空链表或只有一个节点if not head or not head.next:return head# 先反转后面的链表new_head reverseList(head.next)# 将当前节点接到反转后的链表末尾head.next.next headhead.next Nonereturn new_head五、LeetCode 24. 两两交换链表中的节点5.1 题目描述给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。示例输入head [1,2,3,4]输出[2,1,4,3]5.2 方法一迭代法哨兵节点迭代法的关键在于使用一个哨兵节点dummy node 来简化头节点的处理。代码实现Python pythondef swapPairs(head):dummy ListNode(0)dummy.next headprev dummywhile head and head.next: nxt head.next # 保存第二个节点 head.next nxt.next # 第一个节点指向第三个节点 nxt.next head # 第二个节点指向第一个节点 prev.next nxt # 前驱指向新的头节点 prev head # 移动前驱 head head.next # 移动当前指针 return dummy.next复杂度分析时间复杂度O(n)空间复杂度O(1)5.3 方法二递归法递归法是解决本题的优雅方式核心思想是每次只处理链表的前两个节点其余部分交给递归函数继续处理。递归三步走终止条件链表为空或只有一个节点无法交换直接返回递归处理先处理后面的节点后序遍历保证后面的链表已经两两交换完成交换当前两个节点将处理好的子链表接到当前交换后的节点后面代码实现Python pythondef swapPairs(head):# 递归终止条件没有节点或只有一个节点if not head or not head.next:return head# 后序遍历先处理后面的节点 next_level swapPairs(head.next.next) # 交换当前两个节点 ret head.next # 保存第二个节点作为新头 ret.next head # 第二个节点指向第一个节点 head.next next_level # 第一个节点指向后面处理好的链表 return ret # 返回新的头节点代码解读第2-3行递归终止条件当链表为空或只有一个节点时无法交换第6行采用后序遍历先处理后面的节点这样在交换当前两个节点时head.next.next 指向的已经是处理好的子链表第9-11行交换当前两个节点并将处理好的子链表接在后面复杂度分析时间复杂度O(n)空间复杂度O(n)递归调用占用系统栈空间六、递归解题的心法通过以上两道题目的学习我们可以总结出递归解题的通用框架6.1 三步法明确递归函数的定义这个函数要做什么参数是什么返回值是什么确定终止条件什么情况下递归应该结束找到递推关系如何将大问题分解为规模更小的相同问题6.2 注意事项不要陷入调用栈的细节递归的本质是不断重复相同的事情我们应该关注的是一级调用的逻辑而不是去思考完整的调用栈先写终止条件这是递归的出口防止无限递归相信递归只要递归函数定义正确就相信它能处理好子问题6.3 两种题型的对比题目 迭代法特点 递归法特点反转链表 双指针逐个反转 将双指针逻辑转化为递归两两交换 哨兵节点 三个指针 后序遍历先处理后面再交换当前