一、前言
在数据结构与算法的学习过程中，递归和链表是两个绕不开的重要概念。递归是一种优雅的编程思想，而链表则是数据结构的基础之一。当两者相遇，往往能碰撞出精妙的解法。
本文将从递归的基本概念出发，结合链表这一数据结构，详细讲解LeetCode上的两道经典题目——206. 反转链表和24. 两两交换链表中的节点，帮助大家建立起递归解题的思维框架。所有示例代码均使用 Python 实现。
二、递归概述
2.1 什么是递归
递归，简单来说就是在定义一个过程或函数时，出现调用本过程或本函数的情况。用一句经典的故事来理解：
从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事……”
递归根据调用方式可以分为两类：
直接递归：函数直接调用自身
间接递归：函数p调用函数q，而q又调用p
如果一个递归函数中，递归调用语句是最后一条执行语句，则称为尾递归。
2.2 递归模型
一个完整的递归模型由两部分组成：
递归出口：确定递归何时结束，即终止条件
递归体：确定递归求解时的递推关系
以经典的阶乘函数 n! 为例：
python
def factorial(n):
if n == 1: # 递归出口
return 1
return n * factorial(n-1) # 递归体
其递归模型可抽象为：
text
factorial(1) = 1 // 递归出口
factorial(n) = n * factorial(n-1) // 递归体
2.3 斐波那契数列
斐波那契数列是递归的经典应用场景。这个数列从第3项开始，每一项都等于前两项之和：
0，1，1，2，3，5，8，13，21，34，55，89……
其数学定义为：
text
F(0) = 0，F(1) = 1
F(n) = F(n-1) + F(n-2) (n ≥ 2)
用Python实现如下：
python
def fibonacci5(n):
def fn(i):
if i == 1:
return 1
if i == 0:
return 0
else:
return fn(i-2) + fn(i-1)
for i in range(n):
print(fn(i))
2.4 什么时候用递归
以下三种情况常常会用到递归：
定义是递归的（如斐波那契数列）
数据结构是递归的（如链表、树）
问题的求解方法是递归的（如分治算法）
三、链表基础知识
在正式解题之前，我们先回顾一下链表的基本概念。
链表是一种通过指针将一组零散的内存块串联起来的线性数据结构。与数组不同，链表不要求存储在一块连续的内存中，因此对内存的要求更低，但随机访问的性能不如数组。
单链表的每个节点包含两部分：
数据域（val） ：存储数据
指针域（next） ：指向下一个节点
Python 中的链表节点定义：
python
class ListNode:
definit(self, val=0, next=None):
self.val = val
self.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） ：
python
def reverseList(head):
cur = head
pre = None
while cur:
tmp = cur.next # 保存下一个节点
cur.next = pre # 反转指向
pre = cur # pre 前移
cur = tmp # cur 前移
return pre
复杂度分析：
时间复杂度：O(n)，只需遍历一次链表
空间复杂度：O(1)，只使用了常数个指针
4.3 方法二：递归法
递归法同样可以实现链表反转，其思路与迭代法类似，但用递归的方式来实现指针的移动。
代码实现（Python） ：
python
def reverse(pre, cur):
if cur is None:
return pre
tmp = cur.next
cur.next = pre
return reverse(cur, tmp)
def reverseList(head):
return reverse(None, head)
递归思路：reverse(pre, cur) 函数的意义是反转以 cur 为头、pre 为前驱的链表，返回反转后的新头节点。递归的终止条件是 cur == None，此时 pre 就是新链表的头节点。
此外，也可以使用更简洁的单函数递归（后序遍历）版本：
python
def reverseList(head):
# 递归终止条件：空链表或只有一个节点
if not head or not head.next:
return head
# 先反转后面的链表
new_head = reverseList(head.next)
# 将当前节点接到反转后的链表末尾
head.next.next = head
head.next = None
return new_head
五、LeetCode 24. 两两交换链表中的节点
5.1 题目描述
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
5.2 方法一：迭代法（哨兵节点）
迭代法的关键在于使用一个哨兵节点（dummy node） 来简化头节点的处理。
代码实现（Python） ：
python
def swapPairs(head):
dummy = ListNode(0)
dummy.next = head
prev = dummy
while 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） ：
python
def 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 两种题型的对比
题目 迭代法特点 递归法特点
反转链表 双指针逐个反转 将双指针逻辑转化为递归
两两交换 哨兵节点 + 三个指针 后序遍历，先处理后面再交换当前
