定義一個函數，輸入一個鏈表的頭節點，反轉該鏈表并輸出反轉后鏈表的頭節點。 ? 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL ? 限制： 0 <= 節點個數 <= 5000 ## 補充下面的代碼 ``` /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { } } ``` ## 解題思路 解題思路： 如下圖所示，題目要求將鏈表反轉。本文介紹迭代（雙指針）、遞歸兩種實現方法。  方法一：迭代（雙指針） 考慮遍歷鏈表，并在訪問各節點時修改 next 引用指向，算法流程見注釋。 復雜度分析： 時間復雜度 O(N)O(N) ： 遍歷鏈表使用線性大小時間。 空間復雜度 O(1)O(1) ： 變量 pre 和 cur 使用常數大小額外空間。  代碼： ``` class Solution { public ListNode reverseList(ListNode head) { ListNode cur = head, pre = null; while(cur != null) { ListNode tmp = cur.next; // 暫存后繼節點 cur.next cur.next = pre; // 修改 next 引用指向 pre = cur; // pre 暫存 cur cur = tmp; // cur 訪問下一節點 } return pre; } } ``` 方法二：遞歸 考慮使用遞歸法遍歷鏈表，當越過尾節點后終止遞歸，在回溯時修改各節點的 next 引用指向。 recur(cur, pre) 遞歸函數： 終止條件：當 cur 為空，則返回尾節點 pre （即反轉鏈表的頭節點）； 遞歸后繼節點，記錄返回值（即反轉鏈表的頭節點）為 res ； 修改當前節點 cur 引用指向前驅節點 pre ； 返回反轉鏈表的頭節點 res ； reverseList(head) 函數： 調用并返回 recur(head, null) 。傳入 null 是因為反轉鏈表后， head 節點指向 null ； 復雜度分析： 時間復雜度 O(N)O(N) ： 遍歷鏈表使用線性大小時間。 空間復雜度 O(N)O(N) ： 遍歷鏈表的遞歸深度達到 NN ，系統使用 O(N)O(N) 大小額外空間。  代碼： ``` class Solution { public ListNode reverseList(ListNode head) { return recur(head, null); // 調用遞歸并返回 } private ListNode recur(ListNode cur, ListNode pre) { if (cur == null) return pre; // 終止條件 ListNode res = recur(cur.next, cur); // 遞歸后繼節點 cur.next = pre; // 修改節點引用指向 return res; // 返回反轉鏈表的頭節點 } } ``` 作者：jyd 鏈接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/jian-zhi-offer-24-fan-zhuan-lian-biao-die-dai-di-2/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。