企业官网建设流程全解析

前言

递归和链表是数据结构算法里两大高频考点。递归善于把大问题拆解为结构相同的子问题；链表依靠指针完成节点连接。很多链表题目，既可以用迭代循环实现，也可以用递归优雅解决。本文结合基础概念 + LeetCode 206反转链表、LeetCode24两两交换链表节点，使用Python完整演示两种解法，理清递归与链表指针操作的核心思维。

一、递归基础概念

1. 什么是递归
   递归：函数/过程调用自身。
   • 直接递归：函数A直接调用A自己。

• 间接递归：A调用B，B又调用A。

• 尾递归：递归调用是函数最后一条执行语句，执行完递归调用后没有额外运算操作。

递归模型分为两部分：

1. 递归出口（终止条件）：递归什么时候停下来，给出明确结果，防止无限递归栈溢出。

2. 递归体：描述大问题和子问题之间的递推关系，把原问题拆成规模更小的同类子问题。

示例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 1
return n * fact(n-1)

print(fact(5)) #输出120
这是直接递归；注意：return n * fact(n‑1)，递归调用之后还要做乘法，不属于尾递归。真正尾递归要求return直接返回递归调用结果，不再做计算。
示例2：斐波那契数列（兔子问题）
规则：F(0)=0，F(1)=1；n≥2时，F(n)=F(n‑1)+F(n‑2)。
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n-1)+fib(n-2)

for i in range(7):
print(fib(i),end=" ") #0 1 1 2 3 5 8
递归会产生大量重复计算；递归树可以看到大量重复节点，大数据场景效率差，适合理解递归思想，实际开发优先迭代。

什么时候适合用递归

1. 定义本身就是递归：阶乘、斐波那契。

2. 数据结构是递归的：单链表、树。链表 = 头节点 + 剩下的子链表，天然适配递归思维。

3. 求解方法是递归：分治、回溯类算法。

二、单链表基础回顾

单链表节点定义Python：
class ListNode:
definit(self, val=0, next=None):
self.val = val
self.next = next
• val存储节点数据；next保存下一个节点的引用。

• 链表操作最容易踩坑：修改指针前，必须临时保存后继节点，防止链表断链丢失后续数据。

三、LeetCode 206 反转链表

题目：给单链表头节点head，反转链表，返回反转之后新头节点。
例：1→2→3→4→5 →5→4→3→2→1。

解法1：迭代（双指针，面试首选，空间O(1)）

思路：

1. cur指向当前节点；pre初始为None。

2. 循环中先用temp保存cur.next，防止断链。

3. cur.next = pre完成当前节点反转。

4. pre、cur向后移动，直到cur等于None。

5. 循环结束pre就是新链表头。
   from typing import Optional

class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
pre = None
while cur:
temp = cur.next #保存后续链表，不可省略
cur.next = pre #反转指针
pre = cur
cur = temp
return pre
解法2：递归版本

递归出口：链表为空，或者只有一个节点，直接返回head。
递归体：先反转后面子链表，再调整当前节点指针。
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
#递归出口
if head is None or head.next is None:
return head
new_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 pre
temp = cur.next
cur.next = pre
return 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(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

解法2：递归版本

思路：只处理当前前两个节点，剩下交给递归处理。
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
#递归出口：没有节点 或者只剩1个节点
if head is None or head.next is None:
return head
next_node = head.next
head.next = self.swapPairs(next_node.next)
next_node.next = head
return next_node
五、总结对比
题目 迭代 递归
反转链表206 空间O(1)，速度快，面试优先写 空间O(n)栈开销，代码简洁
两两交换24 使用dummy虚拟头节点，统一边界逻辑 递归逻辑简短，适合理解分治思想

递归做题记住两步：

1. 写递归出口：什么情况直接return，不能再往下递归。

2. 相信递归：递归函数可以正确处理规模更小的子问题，本级只需要处理当前层逻辑。
   链表做题记住：改动next之前，一定要临时保存需要用到的节点引用，避免断链丢失链表。