0206. 反轉鏈表 · ttttt

# 0206. 反轉鏈表 ## 題目地址(206. 反轉鏈表) <https://leetcode-cn.com/problems/reverse-linked-list/> ## 題目描述反轉一個單鏈表。 ``` <pre class="calibre18">``` 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL 進階: 你可以迭代或遞歸地反轉鏈表。你能否用兩種方法解決這道題？ ``` ``` ## 前置知識 - [鏈表](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) ## 公司 - 阿里 - 百度 - 騰訊 - adobe - amazon - apple - bloomberg - facebook - microsoft - snapchat - twitter - uber - yahoo - yelp - zenefits ## 思路這個就是常規操作了，使用一個變量記錄前驅 pre，一個變量記錄后繼 next. 不斷更新`current.next = pre` 就好了 ## 關鍵點解析 - 鏈表的基本操作（交換） - 虛擬節點 dummy 簡化操作 - 注意更新 current 和 pre 的位置，否則有可能出現溢出 ## 代碼語言支持：JS, C++, Python,Java JavaScript Code： ``` <pre class="calibre18">``` /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function (head) { if (!head || !head.next) return head; let cur = head; let pre = null; while (cur) { const next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; }; ``` ``` C++ Code： ``` <pre class="calibre18">``` /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prev = NULL; ListNode* cur = head; ListNode* next = NULL; while (cur != NULL) { next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head: return None prev = None cur = head while cur: cur.next, prev, cur = prev, cur, cur.next return prev ``` ``` Java Code: ``` <pre class="calibre18">``` /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null, cur = head; while (cur != null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } } ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) ## 拓展通過單鏈表的定義可以得知，單鏈表也是遞歸結構，因此，也可以使用遞歸的方式來進行 reverse 操作。 > 由于單鏈表是線性的，使用遞歸方式將導致棧的使用也是線性的，當鏈表長度達到一定程度時，遞歸會導致爆棧，因此，現實中并不推薦使用遞歸方式來操作鏈表。 1. 除第一個節點外，遞歸將鏈表 reverse 2. 將第一個節點添加到已 reverse 的鏈表之后 > 這里需要注意的是，每次需要保存已經 reverse 的鏈表的頭節點和尾節點 C++實現 ``` <pre class="calibre18">``` // 普通遞歸 class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* tail = nullptr; return reverseRecursive(head, tail); } ListNode* reverseRecursive(ListNode *head, ListNode *&tail) { if (head == nullptr) { tail = nullptr; return head; } if (head->next == nullptr) { tail = head; return head; } auto h = reverseRecursive(head->next, tail); if (tail != nullptr) { tail->next = head; tail = head; head->next = nullptr; } return h; } }; // （類似）尾遞歸 class Solution { public: ListNode* reverseList(ListNode* head) { if (head == nullptr) return head; return reverseRecursive(nullptr, head, head->next); } ListNode* reverseRecursive(ListNode *prev, ListNode *head, ListNode *next) { if (next == nullptr) return head; auto n = next->next; next->next = head; head->next = prev; return reverseRecursive(head, next, n); } }; ``` ``` JavaScript 實現 ``` <pre class="calibre18">``` var reverseList = function (head) { // 遞歸結束條件 if (head === null || head.next === null) { return head; } // 遞歸反轉子鏈表 let newReverseList = reverseList(head.next); // 獲取原來鏈表的第 2 個節點 newReverseListTail let newReverseListTail = head.next; // 調整原來頭結點和第 2 個節點的指向 newReverseListTail.next = head; head.next = null; // 將調整后的鏈表返回 return newReverseList; }; ``` ``` Python 實現 ``` <pre class="calibre18">``` class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head ans = self.reverseList(head.next) head.next.next = head head.next = None return ans ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) ## 相關題目 - [92.reverse-linked-list-ii](92.reverse-linked-list-ii.html) - [25.reverse-nodes-in-k-groups](25.reverse-nodes-in-k-groups-cn.md) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經37K star啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)