《数据结构与算法——递归与链表的基本概述与练习》

1. 链表的基本知识 (Linked List Basics)

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。课件中重点讲解了两种经典的链表操作题目：

A. 反转链表 (Reverse Linked List)

• 目标：将单链表的头节点 head 进行反转，并返回反转后的新头节点。
• 常规解法（迭代法）：
  1. 定义两个指针：cur 指向头结点，pre 初始化为 null。
  2. 暂存节点：在改变指向之前，必须用 tmp 指针保存 cur->next 节点，防止链表断开。
  3. 反转指向：将 cur->next 指向 pre。
  4. 移动指针：pre 和 cur 向前移动（pre = cur, cur = tmp）。
  5. 结束条件：当 cur 指向 null 时循环结束，此时 pre 指向新的头结点。

B. 两两交换链表中的节点 (Swap Nodes in Pairs)

• 目标：在不改变节点值的情况下，两两交换相邻的节点（例如：1->2->3->4 变为 2->1->4->3）。
• 核心步骤：
  1. 使用 cur 指针定位到待交换的前一个位置。
  2. 步骤一：cur 指向第二个节点（即 cur->next->next）。
  3. 步骤二：第二个节点指向第一个节点。
  4. 步骤三：第一个节点指向后续的节点（即 3）。
  5. 更新 cur 指针位置，继续处理下一对节点。

2. 递归方法的基本思路 (Basic Ideas of Recursion)

A. 递归的定义与分类
递归是指在定义一个过程或函数时，出现调用本过程或本函数的成分。

• 直接递归：函数直接调用自身（如 fun(n) 调用 fun(n-1)）。
• 间接递归：过程 p 调用 q，q 又调用 p。
• 尾递归：递归调用语句是函数中的最后一条执行语句。

B. 递归模型
一个完整的递归算法通常包含两部分：

1. 递归出口 (Base Case)：确定递归何时结束，即明确的终止条件（防止无限循环）。
2. 递归体 (Recursive Body)：确定递归求解时的递推关系（大问题如何拆解为小问题）。

C. 经典递归案例解析
案例 逻辑描述 递归模型/公式
阶乘 (n!) 求 n 的阶乘，可以拆解为 n 乘以 (n-1) 的阶乘。 出口：n==1 时返回 1递归体：fun(n) = fun(n-1) * n
斐波那契数列 又称“兔子数列”。从第3项开始，每一项都等于前两项之和。 出口：F(0)=0, F(1)=1递归体：F(n) = F(n-1) + F(n-2)

D. 递归的应用场景
通常在以下三种情况下会考虑使用递归：

1. 定义是递归的：如数学中的阶乘、斐波那契数列。
2. 数据结构是递归的：如链表（链表节点包含指向下一个节点的指针，结构自相似）、树、图。
3. 问题的求解方法是递归的：如回溯算法、分治法。

练习题
（1）206.反转列表

（2）24.两两交换链表中的节点