Leetcode206-反转链表

Leetcode 206: 反转链表

这是一道非常经典的链表操作题目，要求熟练掌握链表的遍历与指针操作。反转链表是面试中经常出现的题目之一，也是链表题目的基本方法题。

---

题目描述 输入：一个链表的头节点 head。输出：反转后的链表，即将链表中所有的指针方向进行翻转，最后返回新的头节点。

---

示例 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 输入：head = [] 输出：[]

---

解法 1：迭代法 (双指针) 思路 使用双指针方法遍历链表： 一个指针 prev 表示反转后链表的头节点；另一个指针 curr 指向当前节点。 反转操作： 每次用 curr.next = prev 更新指针，反转当前节点与前驱节点之间的指针连接；然后将两个指针分别向后移动：prev = curr，curr = next。 返回链表的新头节点，即左移到最后的 prev 指针。

---

代码模板 class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; // 反转后链表的头，初始为 null ListNode curr = head; // 当前节点 // 遍历链表 while (curr != null) { ListNode next = curr.next; // 保存当前节点的下一个节点 curr.next = prev; // 反转指针连接 prev = curr; // 移动 prev 指针 curr = next; // 移动 curr 指针 } return prev; // 最终 prev 成为新的头节点 } }

---

复杂度分析 时间复杂度：O(n) 遍历链表一次，操作与链表长度成线性关系。 空间复杂度：O(1) 仅使用两个指针，没有额外空间。

---

解法特性 优点：代码清晰，适合面试时快速实现，也是此类问题的首选解法。适用场景：链表中无额外附加条件，线性处理。

---

解法 2：递归法 思路 利用函数的递归调用来构造链表的反转。递归终止条件： 当前节点为 null 或到达链表的尾节点，此时返回该节点作为新的头节点。 递归返回阶段： 将下一节点的 next 指针指回当前节点（即 head.next.next = head），反转当前节点的指针；当前节点的 next 更新为 null，从而断开后续链表。

递归返回后，新头节点会逐层归还至上层调用。

---

代码模板 class Solution { public ListNode reverseList(ListNode head) { // 递归终止条件，返回新的头节点 if (head == null || head.next == null) { return head; } // 递归反转子链表 ListNode newHead = reverseList(head.next); // 反转当前节点与下一节点之间的指针 head.next.next = head; head.next = null; return newHead; // 返回新的头节点 } }

---

复杂度分析 时间复杂度：O(n) 每个节点仅被访问一次。 空间复杂度：O(n) 递归调用栈的深度为链表长度，最坏情况下占用 O(n) 的额外空间。

---

解法特性 优点：代码更加简洁，适用于强调递归能力的题目或比赛。缺点：如果链表过长，递归调用可能导致栈溢出。

---

解法 3：头插法 思路 采用头插法构造反转链表： 使用一个新链表，将原链表的每个节点依次插入到新链表的头部。 操作步骤： 遍历原链表，将当前节点插入新链表的头部。通过头插法不断更新反转后的链表头节点。

---

代码模板 class Solution { public ListNode reverseList(ListNode head) { ListNode newHead = null; // 新链表的头节点 while (head != null) { ListNode next = head.next; // 保存原链表的下一个节点 head.next = newHead; // 当前节点插入到新链表的头部 newHead = head; // 更新新链表的头节点 head = next; // 移动到原链表的下一个节点 } return newHead; // 返回新链表的头节点 } }

---

复杂度分析 时间复杂度：O(n) 遍历链表一次。 空间复杂度：O(1) 原地修改指针，无需额外的栈空间。

---

解法特性 优点：实现过程清晰直观，指针操作较简单。缺点：需要关联到新链表概念，与解法 1 类似，但不直接操作原链表头节点。

---

解法 4：栈 思路 利用栈的 后进先出 (LIFO) 特性存储链表节点。遍历链表时依次将所有节点压入栈。依次弹出栈构造新的链表。

---

代码模板 import java.util.Stack; class Solution { public ListNode reverseList(ListNode head) { Stack<ListNode> stack = new Stack<>(); while (head != null) { stack.push(head); head = head.next; } // 构造新的反转链表 ListNode dummy = new ListNode(0); ListNode curr = dummy; while (!stack.isEmpty()) { curr.next = stack.pop(); curr = curr.next; } curr.next = null; // 手动置尾节点的 next 为 null return dummy.next; } }

---

复杂度分析 时间复杂度：O(n) 遍历链表、压栈和弹栈操作均是线性时间。 空间复杂度：O(n) 需要栈记录链表的所有节点。

---

解法特性 优点：逻辑清晰，适用于对栈操作理解较深的场景。缺点：需要额外的空间存储链表节点。

---

快速 AC 策略 首选解法：迭代法 (解法 1) 时间复杂度 O(n)、空间复杂度 O(1)，实现简单，高效且稳定。是处理链表反转问题时的优先选择解法，也是面试中常见测试的重点。 递归法适用场景：解法 2 在面试或竞赛中，如果面试官特别要求递归实现，采用递归法。注意链表过长可能导致栈溢出的隐患。 特殊场景的备选方案 如果需要展示对其他数据结构的掌握，可以选择 栈实现（解法 4）。头插法（解法 3）本质上是迭代法的变化形式，更适合训练链表的插入操作。

---

总结：链表反转的核心技巧 头节点问题：学会用双指针处理头节点的指针反转。指针操作熟练度：能快速写出 prev, curr, next 的正确更新逻辑。递归与迭代的切换：递归实现清晰，但更需要对栈操作有深刻理解。

熟练掌握以上解法，可以确保在任何场景中快速 AC 本题！