題目描述

給你單鏈表的頭節點 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;
};

思考二（遞歸反轉）

遞歸反轉鏈表的核心是將“整體反轉”拆解為“子鏈表反轉 + 局部指針調整”，利用函數調用棧實現從尾到頭的反轉邏輯：

1. 遞歸函數的定義：reverseList(head) 表示反轉以 head 為頭節點的鏈表，并返回反轉后的新頭節點（即原鏈表的尾節點）。

2. 遞歸的拆解思路：

   • 若要反轉 head 開頭的鏈表，可先遞歸反轉 head.next 開頭的子鏈表，得到新頭節點 newHead（這是原鏈表的尾節點，也是最終結果的頭節點）。
   • 此時子鏈表已完成反轉（head.next 成為子鏈表的尾節點），只需調整 head 與 head.next 的指向：讓 head.next.next = head（子鏈表的尾節點指向原頭節點），再將 head.next = null（原頭節點成為新尾節點）。

3. 終止條件：當 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;
};