一、递归概述递归函数自己调用自己。直接递归函数直接调用自身间接递归A 调用 BB 又调用 A尾递归递归调用是函数的最后一条执行语句递归模型由两部分组成递归出口递归结束的终止条件必须要有不然会无限递归。递归体问题的递推求解关系。示例 1n 的阶乘fun(1)1 #递归出口fun(n)n*fun(n‑1) #递归体适合使用递归的 3 种场景定义本身就是递归阶乘、斐波那契数列数据结构是递归链表、树问题求解思路适合递归斐波那契数规则F (0)0F (1)1从第 3 项开始每一项 前两项相加。0,1,1,2,3,5,8,13……def fibonacci5(n):def fn(i):if i 0:return 0if i 1:return 1else:return fn(i-2)fn(i-1)for i in range(n):print(fn(i))二、反转链表题目把链表节点顺序颠倒1→2→3→4→5变成5→4→3→2→1方法 1双指针迭代思路cur指向当前头结点pre初始为Nonetmp保存 cur 原本的下一个结点防止链表断掉将cur.next指向pre完成局部反转pre、cur向后移动循环直到 cur 为 None返回 prepre 就是反转后的新头结点class Solution:def reverseList(self, head):cur headpre Nonewhile cur:tmp cur.next #保存下一个节点cur.next pre #反转指向pre curcur tmpreturn pre方法 2递归实现反转链表递归逻辑和双指针思路一致递归出口为 cur 等于 None返回 pre 作为新头。class Solution:def reverseList(self, head):return self.reverse(head, None)def reverse(self, cur, pre):if cur None:return pretemp cur.nextcur.next prereturn self.reverse(temp, cur)三、两两交换链表中的节点题目两两交换链表相邻节点不修改节点内部数值只调换节点指针。 示例输入1‑2‑3‑4输出2‑1‑4‑3解题思路使用虚拟头结点dummy_head操作指针完成交换。 循环条件必须同时存在下一个、下下个节点才可以交换。class Solution:def swapPairs(self, head):dummy_head ListNode(nexthead)current dummy_headwhile current.next and current.next.next:temp current.nexttemp1 current.next.next.nextcurrent.next current.next.nextcurrent.next.next temptemp.next temp1current current.next.nextreturn dummy_head.next