题目描述

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

示例 1：
在这里插入图片描述
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
在这里插入图片描述

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

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

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

思考一

遍历链表，把当前节点的后继节点作为新的头节点插入到链表头部，当前节点的后继节点往后挪动。如下图：
在这里插入图片描述

代码

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} head* @return {ListNode}*/
var reverseList = function(head) {if (!head) return head;let headNode = head;let node = head;while (node.next) {let tmp = node.next;node.next = tmp.next;tmp.next = headNode;headNode = tmp;}    return headNode;
};

思考二（递归反转）

递归反转链表的核心是将“整体反转”拆解为“子链表反转 + 局部指针调整”，利用函数调用栈实现从尾到头的反转逻辑：

递归函数的定义：reverseList(head) 表示反转以 head 为头节点的链表，并返回反转后的新头节点（即原链表的尾节点）。
递归的拆解思路：
- 若要反转 head 开头的链表，可先递归反转 head.next 开头的子链表，得到新头节点 newHead（这是原链表的尾节点，也是最终结果的头节点）。
- 此时子链表已完成反转（head.next 成为子链表的尾节点），只需调整 head 与 head.next 的指向：让 head.next.next = head（子链表的尾节点指向原头节点），再将 head.next = null（原头节点成为新尾节点）。
终止条件：当 head 为 null（空链表）或 head.next 为 null（单节点链表）时，无需反转，直接返回 head 本身。

这种思路通过递归将问题规模逐步缩小，利用函数栈的“后入先出”特性，自然实现了从链表尾部到头部的指针反转，代码简洁且符合递归的“分治”思想。时间复杂度为 O(n)（每个节点处理一次），空间复杂度为 O(n)（递归调用栈深度）。

代码

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} head* @return {ListNode}*/
var reverseList = function(head) {// 递归终止条件：空链表或只有一个节点if (head === null || head.next === null) {return head;}// 递归反转当前节点的下一个节点开始的子链表const newHead = reverseList(head.next);// 反转当前节点与下一个节点的指向head.next.next = head;// 断开原指向，避免形成环head.next = null;// 返回新的头节点（即原链表的最后一个节点）return newHead;
};