0092. 反轉鏈表 II · ttttt

# 0092. 反轉鏈表 II ## 題目地址(92. 反轉鏈表 II) <https://leetcode-cn.com/problems/reverse-linked-list-ii/> ## 題目描述 ``` <pre class="calibre18">``` 反轉從位置 m 到 n 的鏈表。請使用一趟掃描完成反轉。說明: 1 ≤ m ≤ n ≤ 鏈表長度。示例: 輸入: 1->2->3->4->5->NULL, m = 2, n = 4 輸出: 1->4->3->2->5->NULL ``` ``` ## 前置知識 - 鏈表 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路（四點法）這道題和[206.reverse-linked-list](https://github.com/azl397985856/leetcode/blob/master/problems/206.reverse-linked-list.md) 有點類似，并且這道題是 206 的升級版。讓我們反轉某一個區間，而不是整個鏈表，我們可以將 206 看作本題的特殊情況（special case）。核心在于**取出需要反轉的這一小段鏈表，反轉完后再插入到原先的鏈表中。** 以本題為例：反轉的是 2,3,4 這三個點，那么我們可以先取出 2，用 cur 指針指向 2，然后當取出 3 的時候，我們將 3 指向 2 的，把 cur 指針前移到 3，依次類推，到 4 后停止，這樣我們得到一個新鏈表 4->3->2, cur 指針指向 4。對于原鏈表來說，有兩個點的位置很重要，需要用指針記錄下來，分別是 1 和 5，把新鏈表插入的時候需要這兩個點的位置。用 pre 指針記錄 1 的位置當 4 結點被取走后，5 的位置需要記下來這樣我們就可以把反轉后的那一小段鏈表加入到原鏈表中 ![](https://img.kancloud.cn/cc/e4/cce4638062603b883631e60f34bfd0e3_956x535.gif) (圖片來自網絡) - 首先我們直接返回 head 是不行的。當 m 不等于 1 的時候是沒有問題的，但只要 m 為 1，就會有問題。 - 其次如果鏈表商都小于 4 的時候，p1，p2，p3，p4 就有可能為空。為了防止 NPE，我們也要充分地判空。 ``` <pre class="calibre18">``` class Solution: def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode: pre = None cur = head i = 0 p1 = p2 = p3 = p4 = None # 一坨邏輯 if p1: p1.next = p3 else: dummy.next = p3 if p2: p2.next = p4 return head ``` ``` 如上代碼是不可以的，我們考慮使用 dummy 節點。 ``` <pre class="calibre18">``` class Solution: def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode: pre = None cur = head i = 0 p1 = p2 = p3 = p4 = None dummy = ListNode(0) dummy.next = head # 一坨邏輯 if p1: p1.next = p3 else: dummy.next = p3 if p2: p2.next = p4 return dummy.next ``` ``` 關于鏈表反轉部分, 順序比較重要，我們需要： - 先 cur.next = pre - 再更新 p2 和 p2.next(其中要設置 p2.next = None，否則會互相應用，造成無限循環) - 最后更新 pre 和 cur 上述的順序不能錯，不然會有問題。原因就在于`p2.next = None`，如果這個放在最后，那么我們的 cur 會提前斷開。 ``` <pre class="calibre18">``` while cur: i += 1 if i == m - 1: p1 = cur next = cur.next if m if i == m: p2 = cur p2.next = None if i == n: p3 = cur if i == n + 1: p4 = cur pre = cur cur = next ``` ``` ## 關鍵點解析 - 四點法 - 鏈表的基本操作 - 考慮特殊情況 m 是 1 或者 n 是鏈表長度的情況，我們可以采用虛擬節點 dummy 簡化操作 - 用四個變量記錄特殊節點，然后操作這四個節點使之按照一定方式連接即可。 - 注意更新 current 和 pre 的位置，否則有可能出現溢出 ## 代碼我把這個方法稱為 `四點法` 語言支持：JS, Python3 JavaScript Code: ``` <pre class="calibre18">``` /* * @lc app=leetcode id=92 lang=javascript * * [92] Reverse Linked List II * * https://leetcode.com/problems/reverse-linked-list-ii/description/ */ /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @param {number} m * @param {number} n * @return {ListNode} */ var reverseBetween = function (head, m, n) { // 虛擬節點，簡化操作 const dummyHead = { next: head, }; let cur = dummyHead.next; // 當前遍歷的節點 let pre = cur; // 因為要反轉，因此我們需要記住前一個節點 let index = 0; // 鏈表索引，用來判斷是否是特殊位置（頭尾位置） // 上面提到的四個特殊節點 let p1 = (p2 = p3 = p4 = null); while (cur) { const next = cur.next; index++; // 對 (m - n) 范圍內的節點進行反轉 if (index > m && index <= n) { cur.next = pre; } // 下面四個if都是邊界, 用于更新四個特殊節點的值 if (index === m - 1) { p1 = cur; } if (index === m) { p2 = cur; } if (index === n) { p3 = cur; } if (index === n + 1) { p4 = cur; } pre = cur; cur = next; } // 兩個鏈表合并起來 (p1 || dummyHead).next = p3; // 特殊情況需要考慮 p2.next = p4; return dummyHead.next; }; ``` ``` Python Code: ``` <pre class="calibre18">``` class Solution: def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode: if not head.next or n == 1: return head dummy = ListNode() dummy.next = head pre = None cur = head i = 0 p1 = p2 = p3 = p4 = None while cur: i += 1 next = cur.next if m if i == m - 1: p1 = cur if i == m: p2 = cur if i == n: p3 = cur if i == n + 1: p4 = cur pre = cur cur = next if not p1: dummy.next = p3 else: p1.next = p3 p2.next = p4 return dummy.next ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) ## 相關題目 - [25.reverse-nodes-in-k-groups](25.reverse-nodes-in-k-groups-cn.md) - [206.reverse-linked-list](206.reverse-linked-list.html) 更多題解可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。 ![](https://img.kancloud.cn/a3/63/a363818092b0356fbd67882f0389528b_900x500.jpg)