单链表反转的常见实现方式有哪些？

### 遍历法（头插法 / 迭代法） **作用** - 从头到尾遍历原链表，把每个结点依次摘下，插入到新链表头部。 - 不复制结点，只修改 `next` 指针，属于原地反转。 - 时间复杂度为 `O(n)`，额外空间复杂度为 `O(1)`。 **原理** 1. 如果链表为空或只有一个结点，直接返回原头结点。 2. 使用 `current` 指向当前结点，`next` 暂存当前结点的后继，防止断链。 3. 使用 `reverseHead` 表示反转后新链表的头结点。 4. 每轮循环执行： - `next = current.next`：先保存后继； - `current.next = reverseHead`：让当前结点指向新链表头部； - `reverseHead = current`：更新新链表头； - `current = next`：继续处理原链表的下一个结点。 5. 遍历结束后，`reverseHead` 就是反转后的头结点。 另一种常见遍历写法使用 `pre`、`cur`、`next` 三个指针：`cur` 不断指向 `pre`，然后双指针一起向后移动，最后把原头结点的 `next` 置空。本质仍是迭代反转，时间和空间复杂度相同。 ### 递归法 **作用** - 先递归处理当前结点后面的剩余链表，再在递归返回的过程中逐层修改指针。 - 代码更简洁，但会使用递归调用栈。 - 时间复杂度为 `O(n)`，额外空间复杂度为 `O(n)`。 **原理** 1. 递归终止条件：当前结点为 `null`，或当前结点已经是尾结点，即 `current.next == null`，直接返回当前结点。 2. 先用 `nextNode` 保存当前结点的下一个结点。 3. 可先将 `current.next` 置空，避免链表形成环。 4. 递归反转子链表 `nextNode` 及其后续部分。 5. 递归返回后，让后继结点指回当前结点：`nextNode.next = current`。 6. 递归始终返回原链表的尾结点，也就是反转后的新头结点。 例如 `1 -> 2 -> 3 -> 4`，会先递归到结点 `4`，再在返回过程中依次设置 `4.next = 3`、`3.next = 2`、`2.next = 1`，最终得到 `4 -> 3 -> 2 -> 1`。

# 作用 单链表反转的本质不是复制或重建节点，而是**改变每个节点的 `next` 指针方向**。常见实现主要有两种： - **迭代头插法** - 借助虚拟头节点 `dummy`，逐个把当前节点插入到 `dummy` 后面。 - 时间复杂度：`O(n)` - 空间复杂度：`O(1)` - **递归法** - 先递归反转当前节点后面的链表，再把当前节点接到反转后链表的末尾。 - 时间复杂度：`O(n)` - 空间复杂度：`O(n)`，主要来自递归调用栈。 # 原理 ## 1. 迭代头插法 创建虚拟头节点 `dummy`，令 `dummy.next = null`，然后从原链表头节点开始遍历： 1. 保存当前节点的后继节点 `next = curr.next`，避免断链。 2. 让当前节点指向已反转部分的头节点：`curr.next = dummy.next`。 3. 把当前节点接到虚拟头节点之后：`dummy.next = curr`。 4. 移动到原先保存的后继节点，继续处理。 遍历结束后，`dummy.next` 就是反转后的新头节点。 核心顺序可以概括为： - 先保存后继； - 再修改指针； - 最后移动游标。 以 `1 → 2 → 3` 为例： - 处理节点 `1` 后：`dummy → 1 → null` - 处理节点 `2` 后：`dummy → 2 → 1 → null` - 处理节点 `3` 后：`dummy → 3 → 2 → 1 → null` ## 2. 递归法 递归的思路是把问题缩小： 1. 对于当前节点 `head`，先递归反转 `head.next` 开始的剩余链表。 2. 剩余链表反转后，原来的后继节点 `head.next` 变成了反转部分的尾节点。 3. 执行： - `head.next.next = head`，让原后继反向指向当前节点； - `head.next = null`，断开当前节点原来的正向连接。 4. 递归逐层返回新的头节点。 递归终止条件通常是： - 当前节点为 `null`；或 - 当前节点已经是尾节点，即 `head.next == null`。 递归法代码较简洁，但会使用 `O(n)` 的调用栈空间；链表较长时可能产生栈溢出风险。