反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

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

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

输入：head = [] 输出：[]

简单做法：迭代循环使用数组反转再生成新链表

进阶做法：使用迭代法或递归法。

方法一：迭代法

核心思路：
遍历链表，逐个改变节点的指针方向，将当前节点指向前驱节点。需维护三个指针：前驱节点（prev）、当前节点（curr）和后继节点（next）。

步骤：

初始化 prev 为 null，curr 为头节点。
遍历链表，每次迭代中：
- 保存当前节点的后继节点 next。
- 将当前节点的 next 指针指向前驱节点 prev。
- 更新 prev 和 curr 指针，继续遍历。
遍历结束后，prev 即为新链表的头节点。

代码实现：

function reverseList(head) {
    let prev = null;
    let curr = head;
    
    while (curr) {
        const next = curr.next; // 保存后继节点
        curr.next = prev;       // 反转指针
        prev = curr;            // 移动prev
        curr = next;            // 移动curr
    }
    
    return prev; // 返回新头节点
}

复杂度分析：

时间复杂度：O(n)，遍历链表一次。
空间复杂度：O(1)，仅需常数级额外空间。

方法二：递归法

核心思路：
递归反转后续节点，然后调整当前节点与后继节点的指针关系。

步骤：

终止条件：若当前节点为空或无后继节点，直接返回当前节点。
递归处理：递归反转后续节点，得到新的头节点 newHead。
调整指针：将当前节点的后继节点的 next 指向当前节点，然后将当前节点的 next 置为 null。

代码实现：

function reverseList(head) {
    if (!head || !head.next) return head;
    
    const newHead = reverseList(head.next); // 递归反转后续节点
    head.next.next = head;  // 调整指针：后继节点的next指向当前节点
    head.next = null;       // 当前节点的next置为null
    
    return newHead; // 返回新头节点
}

复杂度分析：

时间复杂度：O(n)，需遍历链表一次。
空间复杂度：O(n)，递归栈深度为链表长度（可能导致栈溢出）。

示例验证

输入链表：1 → 2 → 3 → 4 → 5

迭代法过程：

初始：prev = null, curr = 1
第一次迭代：1 → null，prev = 1, curr = 2
第二次迭代：2 → 1 → null，prev = 2, curr = 3
第三次迭代：3 → 2 → 1 → null，prev = 3, curr = 4
第四次迭代：4 → 3 → 2 → 1 → null，prev = 4, curr = 5
第五次迭代：5 → 4 → 3 → 2 → 1 → null，prev = 5, curr = null
返回 prev = 5，即反转后的头节点。

递归法过程：

递归到节点 5，返回 5 作为 newHead。
回溯到节点 4：5 → 4 → null，返回 5。
回溯到节点 3：5 → 4 → 3 → null，返回 5。
回溯到节点 2：5 → 4 → 3 → 2 → null，返回 5。
回溯到节点 1：5 → 4 → 3 → 2 → 1 → null，返回 5。

总结

迭代法：直观高效，空间复杂度优，推荐使用。
递归法：代码简洁，但可能导致栈溢出，适用于链表较短的场景。

方法一：迭代法​

方法二：递归法​

示例验证​

总结​

方法一：迭代法

方法二：递归法

示例验证

总结