Leetcode【86、92、148、206】

2019 年 10 月 29 日
筆記

問題描述：【Linked List】86. Partition List 解題思路：

這道題是給一個鏈表和整數 x，將小於 x 的數按位置順序放在鏈表左側，大於等於 x 的按位置順序放在右側。

類似於快排的劃分過程有木有。可以建立兩個指針 l_end 和 r_end，分別指向 x 的左右兩部分的尾部。再建立一個指針指向當前結點 cur，便於鏈表的遍歷。因為我們不知道第一個結點和 x 的關係，所以可以建一個空結點 node 指向 head，最後 head.next 就是答案。

l_end 初始化為 head（空結點），r_end 初始化為 None，cur 指向 head.next 第一個結點；
遍歷 cur： 1、如果 cur.val < x and r_end == None，說明剛開始碰到的都是小於 x 的，就只需要移動 l_end 到 cur 的位置即可； 2、如果 cur.val < x，這個時候 r_end 不為空，利用這三個指針進行交換和移動即可； 3、否則，碰到的都是大於等於 x 的，就只需要移動 r_end 到 cur 的位置即可。

時間複雜度為 O(n)，空間複雜度為 O(1)。

Python3 實現：

# Definition for singly-linked list.  # class ListNode:  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution:      def partition(self, head: ListNode, x: int) -> ListNode:          node = ListNode(-1)  # 頭結點          node.next = head          head = node          l_end, r_end, cur = head, None, head.next          while cur:              if cur.val < x and r_end == None:  # 沒遇到比 x 大的，只移動 l_end                  l_end = cur              elif cur.val < x:  # r_end 不為 None，利用三指針交換                  r_end.next = cur.next  # 交換                  cur.next = l_end.next                  l_end.next = cur                  l_end = cur  # 移動                  cur = r_end              else:                  r_end = cur              cur = cur.next          return head.next

問題描述：【Linked List】92. Reverse Linked List II 解題思路：

這道題是給一個鏈表和區間 [m, n]，反轉區間內的數字。

這道題和下面的 Leetcode 206 思路相同。對於一個區間的反轉，需要用 notr 記錄不用反轉區間的最後一個位置；用 start 記錄反轉區間的頭指針；為了反轉方便，再定義 pre 和 cur 分別為前一個指針和當前指針。遍歷 cur，找到反轉區間，進行指針的交換和移動操作即可。

時間複雜度為 O(n)，空間複雜度為 O(1)。

Python3 實現：

# Definition for singly-linked list.  # class ListNode:  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution:      def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:          if not head:              return head          # notr: 不用反轉區間的最後一個位置          # start: 反轉區間的頭指針          # pre, cur：前一個指針和當前指針          notr, start, pre, cur = None, None, None, head          i = 1          while cur:              if i <= m:                  if i == m:  # 初始化四個指針                      notr = pre                      start = cur                  pre = cur                  cur = cur.next              elif m < i <= n:  # 在起始位置的下一個位置反轉，通過指針交換完成                  pre.next = cur.next # 交換                  cur.next = start                  start = cur                  if m == 1:  # 從頭開始                      head = cur                  else:  # 從中間開始                      notr.next = start                  cur = pre.next  # 移動              else:                  break              i += 1          return head

問題描述：【Linked List】148. Sort List 解題思路：

這道題是給一個鏈表，對鏈表排序。要求時間複雜度 O(nlogn)，空間複雜度 O(1)。

首先，肯定能想到要麼是使用快速排序，要麼是歸併排序。剛好上面的 Leetcode 86 為鏈表劃分，所以就藉助其思想實現了快排。但是最後一個 case 超時了（嚶嚶嚶），程式碼如下：

Python3 實現：

# Definition for singly-linked list.  # class ListNode:  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution:      def sortList(self, head: ListNode) -> ListNode:          if not head or not head.next:  # 遞歸出口              return head          pivot = head.val          le, ri, cur = head, None, head.next  # 左右區間劃分          while cur:              if cur.val < pivot and ri == None:                  le = cur              elif cur.val < pivot:                  ri.next = cur.next  # 交換                  cur.next = le.next                  le.next = cur                  le = cur  # 移動                  cur = ri              else:                  ri = cur              cur = cur.next          ri = le.next  # 左右兩側排序          le.next = None          lp = self.sortList(head.next)          rp = self.sortList(ri)          if lp == None:   # 將基準 head.val 放到中間              head.next = rp              lp = head          else:              cur = lp              while cur.next:                  cur = cur.next              cur.next = head              head.next = rp          return lp  # 返回鏈表頭結點

看了題解，有人使用歸併排序 mergeSort 通過了，同樣可以做到時間複雜度為 O(nlogn)，空間複雜度為 O(1)。程式碼如下（不是我寫的，懶得再寫一次了）：

# Definition for singly-linked list.  # class ListNode:  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution:      def sortList(self, head: ListNode) -> ListNode:          if head is None:              return None          p, i = head, 0          while p:              i += 1              p = p.next          return self.mergeSort(head, i)[0]        def mergeSort(self,head,k):          if k == 1:              next = head.next              head.next = None              return head, next          left_head, next = self.mergeSort(head, k//2)          right_head, next = self.mergeSort(next, k-(k//2))          return self.merge(left_head, right_head), next        def merge(self, h1, h2):          dummy = ListNode(0)          p = dummy          while h1 and h2:              if h1.val <= h2.val:                  p.next = h1                  p = p.next                  h1 = h1.next              else:                  p.next = h2                  p = p.next                  h2 = h2.next          if h1 is None and h2 is not None:              p.next = h2          elif h2 is None and h1 is not None:              p.next = h1          return dummy.next

問題描述：【Linked List】206. Reverse Linked List 解題思路：

這道題是給一個鏈表，將鏈表反轉。

鏈表反轉只需要兩個相鄰指針 pre 和 cur 即可。對於 cur 遍歷，先交換（3 次操作）後移動指針到正確的位置，時間複雜度為 O(n)。

Python3 實現：

# 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 head          pre, cur = head, head.next          while cur:              pre.next = cur.next  # 交換              cur.next = head              head = cur              cur = pre.next  # 移動          return head

Tags: