Reverse Linked List（反转链表）

题目 / Problem

中文： 给定一个单链表的头节点 head，反转链表并返回反转后的链表。

English: Given the head of a singly linked list, reverse the list and return the reversed list.

示例 / Examples

Example 1

Input:  head = [1,2,3,4,5]
Output: [5,4,3,2,1]

反转前 / Before:
1 → 2 → 3 → 4 → 5 → null

反转后 / After:
null ← 1 ← 2 ← 3 ← 4 ← 5
                         ↑
                       head

Example 2

Input:  head = [1,2]
Output: [2,1]

1 → 2 → null

2 → 1 → null

Example 3

Input:  head = []
Output: []

约束 / Constraints

• 链表中的节点数在 [0, 5000] 范围内。
  The number of nodes in the list is in the range [0, 5000].
• -5000 <= Node.val <= 5000

进阶 / Follow-up

链表既可以通过迭代方式反转，也可以通过递归方式反转。请实现这两种方法。
A linked list can be reversed either iteratively or recursively. Implement both approaches.

解题思路一：迭代 / Approach 1: Iteration

遍历链表，并将每个节点的 next 指针改为指向它的前一个节点。需要维护三个指针：
Traverse the list and redirect each node's next pointer to its previous node. Maintain three pointers:

• previous：已经反转部分的头节点，也是当前节点反转后应指向的节点。
  previous: the head of the reversed portion and the node the current node should point to.
• current：当前正在处理的节点。
  current: the node currently being processed.
• next：提前保存的下一个节点，防止修改 current.next 后丢失未处理部分。
  next: the next node saved before changing current.next, preventing loss of the unprocessed portion.

每轮执行以下操作：
Perform these steps in every iteration:

1. next = current.next       保存后继节点 / Save the next node
2. current.next = previous  反转当前指针 / Reverse the current pointer
3. previous = current       前移 previous / Advance previous
4. current = next           前移 current / Advance current

当 current 变为 null 时，previous 指向原链表的最后一个节点，也就是反转后链表的新头节点。
When current becomes null, previous points to the original tail, which is the new head of the reversed list.

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *   this.val = val ?? 0;
 *   this.next = next ?? null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function reverseList(head) {
  let previous = null;
  let current = head;

  while (current !== null) {
    const next = current.next;
    current.next = previous;
    previous = current;
    current = next;
  }

  return previous;
}

执行过程 / Walkthrough

以 head = [1,2,3,4,5] 为例：
For head = [1,2,3,4,5]:

遍历结束后返回 previous，即节点 5。
After traversal, return previous, which points to node 5.

复杂度 / Complexity

设链表中有 n 个节点。
Let the linked list contain n nodes.

• 时间复杂度：O(n)，每个节点只处理一次。
  Time: O(n), because every node is processed once.
• 空间复杂度：O(1)，只使用常数个额外指针。
  Space: O(1), because only a constant number of extra pointers is used.

解题思路二：递归 / Approach 2: Recursion

递归解法先反转从第二个节点开始的子链表，再将当前头节点接到子链表末尾。
The recursive approach first reverses the sublist beginning at the second node, then attaches the current head to the end of that reversed sublist.

对于链表：
For the list:

1 → 2 → 3 → null

递归返回已经反转的子链表：
The recursive call returns the reversed sublist:

1 → 2 ← 3

然后执行：
Then perform:

head.next.next = head;
head.next = null;

得到：
This produces:

3 → 2 → 1 → null

JavaScript 实现 / JavaScript Implementation

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function reverseListRecursive(head) {
  if (head === null || head.next === null) {
    return head;
  }

  const newHead = reverseListRecursive(head.next);

  head.next.next = head;
  head.next = null;

  return newHead;
}

递归终止条件 / Base Case

• head === null：空链表，直接返回 null。
  An empty list returns null.
• head.next === null：只有一个节点，它已经是反转后链表的头节点。
  A single node is already the head of the reversed list.

为什么要设置 head.next = null？ / Why Set head.next = null?

执行 head.next.next = head 后，原来的后继节点已经反向指回 head。如果不清空原来的 head.next，两个节点会互相指向并形成环。
After head.next.next = head, the original next node points back to head. Without clearing head.next, the two nodes would point to each other and form a cycle.

递归复杂度 / Recursive Complexity

• 时间复杂度 / Time: O(n)
• 空间复杂度 / Space: O(n)，递归调用栈中最多保存 n 层。
  The recursion stack may contain up to n frames.

由于链表最多包含 5000 个节点，某些 JavaScript 运行环境可能因递归层数过深而发生调用栈溢出，因此迭代解法更加稳妥。
Because the list may contain 5000 nodes, some JavaScript runtimes may overflow the call stack with deep recursion, making the iterative solution safer.

迭代与递归对比 / Iteration vs. Recursion

迭代解法通常是本题更推荐的实现。
The iterative approach is generally preferred for this problem.

易错点 / Common Pitfalls

• 修改 current.next 之前必须先保存 current.next，否则会丢失剩余链表。
  Save current.next before modifying it, or the remainder of the list will be lost.
• 迭代结束后应返回 previous，此时 current 已经是 null。
  Return previous after iteration; current is already null.
• previous 必须初始化为 null，这样原头节点才能成为新链表的尾节点。
  Initialize previous to null so the original head becomes the new tail.
• 递归解法中必须执行 head.next = null，否则可能形成环。
  In the recursive solution, set head.next = null or a cycle may form.
• 空链表和单节点链表不需要额外处理，两个实现都应原样返回。
  Empty and single-node lists require no reversal and should be returned as-is.