🚧 第一步：理解链表的结构

链表就像一列火车，每节车厢（节点）有两个部分：

1. 值（val）：比如存储的数字。
2. 下一节的连接（next）：指向下一节车厢的“钩子”（指针）。

在 Python 中，可以用类表示：

python
展开代码
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val       # 值
        self.next = next     # 指向下一个节点的指针

例如，链表 1 -> 2 -> 3 就是三个节点，每个的“钩子”连向下一个。

---

🔄 第二步：反转链表的直观理解

反转链表就是把所有“钩子”的方向调转。比如：

展开代码
原链表：1 -> 2 -> 3 -> None
反转后：3 -> 2 -> 1 -> None

每个节点的“钩子”从指向下一个，变成指向前一个。

---

🔁 第三步：迭代法（最基础的方法）

✅ 核心思想：

逐个节点调整指针方向，需要三个变量帮忙记录位置。

📌 变量说明：

• prev：记录前一个节点，初始是空（None）。
• current：当前处理的节点，初始是头节点。
• next_node：临时保存下一个节点，防止“钩子”断了找不到路。

🔄 步骤：

1. 每次循环：

   • 先记住下一个节点（next_node = current.next）
   • 把当前节点的“钩子”指向前一个（current.next = prev）
   • prev 和 current 都往后移动一步

2. 当 current 为空时，prev 就是新头节点。

💻 代码实现：

python
展开代码
def reverseList(head):
    prev = None
    current = head
    while current:
        next_node = current.next  # 先记住下一个节点
        current.next = prev       # 反转指针
        prev = current            # prev 移到当前节点
        current = next_node       # current 移到下一个节点
    return prev  # 循环结束，prev 是新的头

🧠 例子解释：

反转 1 -> 2 -> 3：

• 初始：prev=None, current=1
• 第1步：保存 2，1 指向 None，prev=1，current=2
• 第2步：保存 3，2 指向 1，prev=2，current=3
• 第3步：保存 None，3 指向 2，prev=3，current=None 结束循环。最终链表是 3 -> 2 -> 1

---

🧠 第四步：递归法（从后往前调整）

✅ 核心思想：

先让后面的节点反转好，再调整当前节点。

🧩 步骤：

1. 终止条件：如果链表为空或只有一个节点，直接返回。
2. 递归步骤：
   • 先递归处理头节点的下一个节点（比如处理 2 -> 3，反转成 3 -> 2）。
   • 此时，头节点 1 的下一个节点 2 已经指向 None，需要让 2 指向 1，然后 1 指向 None。

💻 代码实现：

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

🧠 例子解释：

反转 1 -> 2 -> 3：

• 递归到 3 时返回，new_head=3
• 回到 2 的递归层：让 2.next（3） 指向 2，2 指向 None，此时链表是 3 -> 2 -> None
• 回到 1 的递归层：让 1.next（2） 指向 1，1 指向 None，最终链表是 3 -> 2 -> 1 -> None

---

⚖️ 第五步：两种方法对比

方法	时间复杂度	空间复杂度	优点	缺点
迭代法	O(n)	O(1)	效率高，适合长链表	逻辑稍复杂
递归法	O(n)	O(n)	代码简洁，易于理解	可能栈溢出，空间占用大

---

🧪 第六步：测试验证

用辅助函数将链表转为列表，方便验证：

python
展开代码
def list_to_array(head):
    res = []
    while head:
        res.append(head.val)
        head = head.next
    return res

# 测试
# 创建链表 1->2->3
head = ListNode(1, ListNode(2, ListNode(3)))
reversed_head = reverseList(head)
print(list_to_array(reversed_head))  # 输出 [3, 2, 1]

---

🎯 总结

• 迭代法：边遍历边调整指针，效率高，推荐使用。
• 递归法：代码简洁，但空间占用大，理解递归有助于提升思维。

通过逐步调整指针方向，无论是迭代还是递归，最终都能实现链表的反转。理解指针的变化是关键！