链表反转：单链表反转的方法，递归和迭代实现

一、什么是单链表？¶

在开始之前，我们需要先了解一下单链表的基本结构。单链表是一种常见的数据结构，由多个节点（Node）组成。每个节点包含两部分：数据域（存储数据）和指针域（存储指向下一个节点的地址，在 Python 中通常用 next 表示）。链表的第一个节点称为“头节点”，最后一个节点的指针域通常指向 None（表示链表结束）。

举个例子，一个简单的单链表可以表示为：1 -> 2 -> 3 -> None，其中 1 是头节点，每个箭头表示 next 指针的指向。

二、为什么要反转链表？¶

反转链表是一个常见的操作，比如：
- 需要逆序输出链表中的数据（例如打印链表时从尾到头）；
- 解决某些算法问题（如判断回文链表、两数相加时处理低位在前等）；
- 优化链表操作（如反转后便于某些重复操作）。

三、迭代法反转单链表（推荐初学者入门）¶

核心思路¶

迭代法的核心是遍历链表，逐个反转节点的指针方向。我们需要维护三个指针：prev（前一个节点）、current（当前节点）和 next（下一个节点），通过循环移动这三个指针，逐步将每个节点的 next 指针从指向下一个节点改为指向前一个节点。

步骤详解¶

1. 初始化指针：prev 初始化为 None（反转后链表的末尾），current 初始化为头节点 head。
2. 遍历链表：当 current 不为 None 时，执行以下操作：
   - 保存 current.next（即下一个节点）到 next 变量中（防止后续修改指针后丢失后续节点）；
   - 将 current.next 指向 prev（反转当前节点的指针）；
   - 将 prev 移动到 current（prev 成为新的“前一个节点”）；
   - 将 current 移动到 next（current 成为新的“当前节点”）；
3. 终止条件：当 current 为 None 时，prev 就是反转后链表的头节点。

举个例子（1->2->3->None）¶

我们以链表 1 -> 2 -> 3 -> None 为例，一步步演示反转过程：

• 初始状态：prev = None，current = 1，next = ?
• 第一步：保存 next = current.next = 2；current.next = prev = None（此时链表变为 1 -> None）；prev = current = 1；current = next = 2。
• 第二步：保存 next = current.next = 3；current.next = prev = 1（此时链表变为 2 -> 1 -> None）；prev = current = 2；current = next = 3。
• 第三步：保存 next = current.next = None；current.next = prev = 2（此时链表变为 3 -> 2 -> 1 -> None）；prev = current = 3；current = next = None。
• 终止：current 为 None，反转完成，新头节点是 prev = 3。

代码实现（Python 示例）¶

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_iterative(head):
    prev = None
    current = head
    while current is not None:
        next_node = current.next  # 保存下一个节点
        current.next = prev       # 反转当前节点的指针
        prev = current            # prev 后移
        current = next_node       # current 后移
    return prev  # prev 此时是新的头节点

四、递归法反转单链表（理解递归思想）¶

递归法的核心是先反转当前节点之后的链表，再将当前节点接到反转后的链表末尾。递归的关键是理解“将问题分解为更小的子问题”，并明确递归的终止条件和递归步骤。

核心思路¶

1. 终止条件：如果链表为空（head is None）或只有一个节点（head.next is None），直接返回原链表头节点（无需反转）。
2. 递归步骤：
   - 递归调用 reverse(head.next)，得到反转后的子链表头节点 new_head；
   - 将当前节点 head 的 next 指针（原本指向子链表头节点）改为指向 head 的前一个节点（即反转后的子链表末尾）；
   - 将当前节点 head 的 next 设为 None（使其成为反转后的尾节点）；
   - 返回反转后的子链表头节点 new_head。

举个例子（1->2->3->None）¶

以链表 1 -> 2 -> 3 -> None 为例，递归过程如下：

• 初始调用：reverse(1)
• 递归调用 reverse(2)，得到子链表反转后的头节点 new_head = 3（此时子链表为 3 -> 2 -> None）。
• 处理当前节点 1：原 head.next 是 2，现在需要让 2.next = 1（将 1 接到子链表末尾）；1.next = None（1 成为尾节点）。
• 返回 new_head = 3，最终反转后的链表为 3 -> 2 -> 1 -> None。

代码实现（Python 示例）¶

def reverse_recursive(head):
    # 终止条件：空链表或只有一个节点
    if head is None or head.next is None:
        return head
    # 递归反转后面的子链表
    new_head = reverse_recursive(head.next)
    # 将当前节点接到反转后的子链表末尾
    head.next.next = head
    # 当前节点变为尾节点，next 设为 None
    head.next = None
    return new_head  # 返回反转后的头节点

五、总结¶

两种方法对比¶

关键注意点¶

• 迭代法：必须注意指针移动的顺序（先保存 next，再反转指针，再移动 prev 和 current）。
• 递归法：需明确终止条件（空链表或单节点链表直接返回），并理解“子问题反转后如何连接当前节点”。

通过这两种方法，我们掌握了单链表反转的核心思想。迭代法适合初学者直接理解指针操作，递归法则能帮助理解递归思想在链表问题中的应用。多动手画图模拟指针移动过程，就能轻松掌握链表反转的精髓！