企业官网建设流程全解析

一、递归概述

递归：函数自己调用自己。

• 直接递归：函数直接调用自身
• 间接递归：A 调用 B，B 又调用 A
• 尾递归：递归调用是函数的最后一条执行语句

递归模型由两部分组成：

1. 递归出口：递归结束的终止条件，必须要有，不然会无限递归。
2. 递归体：问题的递推求解关系。

示例 1：n 的阶乘

fun(1)=1 #递归出口

fun(n)=n*fun(n‑1) #递归体

适合使用递归的 3 种场景

1. 定义本身就是递归（阶乘、斐波那契数列）
2. 数据结构是递归（链表、树）
3. 问题求解思路适合递归

斐波那契数

规则：F (0)=0，F (1)=1，从第 3 项开始，每一项 = 前两项相加。0,1,1,2,3,5,8,13……

def fibonacci5(n):

def fn(i):

if i == 0:

return 0

if i == 1:

return 1

else:

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：双指针迭代

思路：

1. cur指向当前头结点，pre初始为None
2. tmp保存 cur 原本的下一个结点，防止链表断掉
3. 将cur.next指向pre完成局部反转
4. pre、cur向后移动，循环直到 cur 为 None
5. 返回 pre，pre 就是反转后的新头结点

class Solution:

def reverseList(self, head):

cur = head

pre = None

while cur:

tmp = cur.next #保存下一个节点

cur.next = pre #反转指向

pre = cur

cur = tmp

return 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 pre

temp = cur.next

cur.next = pre

return self.reverse(temp, cur)

三、两两交换链表中的节点

题目：两两交换链表相邻节点，不修改节点内部数值，只调换节点指针。 示例：输入1‑>2‑>3‑>4，输出2‑>1‑>4‑>3

解题思路：使用虚拟头结点dummy_head，操作指针完成交换。 循环条件：必须同时存在下一个、下下个节点，才可以交换。

class Solution:

def swapPairs(self, head):

dummy_head = ListNode(next=head)

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