算法学习｜递归原理与链表经典题：反转链表、两两交换节点

一、递归基础概念1. 什么是递归递归函数直接或者间接调用自身。直接递归函数自己调用自己。间接递归函数 A 调用 B函数 B 回过头调用 A。尾递归递归调用是函数体内最后一条执行语句。递归模型由两部分构成 ✅递归出口终止条件递归什么时候结束避免无限递归。 ✅递归体描述问题递推、分解的关系。示例阶乘递归数学模型fun(1) 1 #递归出口 fun(n) n * fun(n‑1) #递归体逻辑求 n 的阶乘等价于n × (n‑1)!不断拆解直到 n 等于 1 停止递归。2. 适合使用递归的三类场景定义本身是递归阶乘、斐波那契数列数据结构是递归链表、树一个节点会指向同类型的其他节点问题求解方法是递归分治回溯类问题把大问题拆成结构相同的子问题。3. 斐波那契数列兔子问题故事背景兔子繁殖问题又叫做兔子数列。 规则F (0)0F (1)1从第 3 项开始每一项等于前面两项之和\(F(n)F(n‑1)F(n‑2)\)。 数列0,1,1,2,3,5,8,13,21……递归实现Pythondef fib(n): if n 0: return 0 if n 1: return 1 return fib(n-1)fib(n-2)缺点原始递归存在大量重复计算时间复杂度高。二、LeetCode206 反转链表题目给你单链表头节点把链表整体反转返回反转后的新头节点。 示例1→2→3→4→5 → 5→4→3→2→1解法 1双指针迭代法常规写法核心思路cur指向当前节点pre初始为None使用tmp临时保存 cur 原本的下一个节点防止链表断裂将cur.next指向pre完成当前节点反转pre移动到 cur 位置cur移动到保存好的 tmpcur 走到 None 循环结束pre就是新链表头。Python 完整代码# Definition for singly-linked list. class ListNode(object): def __init__(self, val0, nextNone): self.val val self.next next class Solution(object): def reverseList(self, head): cur head pre None while cur: tmp cur.next #保存下一个节点 cur.next pre #反转指向 pre cur cur tmp return pre时间复杂度 \(O(n)\)遍历链表一次空间复杂度 \(O(1)\)解法 2递归写法递归逻辑和迭代思路保持一致不断向后传递cur和pre直到 cur 为空返回新头节点 pre。class Solution(object): def reverseList(self, head): def reverse(cur, pre): if cur is None: return pre tmp cur.next cur.next pre return reverse(tmp, cur) return reverse(head, None)时间复杂度\(O(n)\)空间复杂度\(O(n)\)递归调用栈消耗空间。对比迭代使用额外变量递归利用函数调用栈完成向后遍历。三、LeetCode24 两两交换链表中的节点题目给定链表两两交换相邻节点不修改节点内部的值只能交换节点本身。 示例输入1‑2‑3‑4输出2‑1‑4‑3。解题关键点使用虚拟头结点 dummy_head简化头部节点交换逻辑循环条件必须同时存在下一个、下下个节点才可以进行两两交换需要临时保存被交换的两个节点防止链表指针丢失。Python 代码实现class ListNode(object): def __init__(self, val0, nextNone): self.val val self.next next class Solution(object): def swapPairs(self, head): dummy_head ListNode(nexthead) current dummy_head #必须有下一个和下下个节点才能够交换 while current.next and current.next.next: temp current.next #保存节点1 temp1 current.next.next.next #保存后续链表 current.next current.next.next #dummy指向节点2 current.next.next temp #节点2指向节点1 temp.next temp1 #节点1接上后面链表 current current.next.next #向后移动两步 return dummy_head.next时间复杂度\(O(n)\)空间复杂度\(O(1)\)注意指针修改顺序如果顺序写错链表直接断开。四、例题