Leetcode【61、82、83、142、143、1171】

2019 年 10 月 29 日
筆記

問題描述：【Linked List】61. Rotate List 解題思路：

這道題是給一個鏈表，旋轉鏈表，將鏈表每個結點向右移動 k 個位置。

1、先計算鏈表長度 size，k = k % size，如果 k % size == 0，則不用移動，直接返回 head； 2、否則，需要將前 size – k 個結點移動到後面。因此只需要循環 size – k 次，找到新鏈表頭部，然後進行指針的交換。最後返回新鏈表頭即可。

注意：這道題雖然是旋轉鏈表，但是實際上並沒有真正的進行結點的移動，只是進行了指針的交換。

時間複雜度為 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 rotateRight(self, head: ListNode, k: int) -> ListNode:          if not head:              return head          cur, size = head, 1          while cur.next:  # cur 結束後記錄鏈表尾              size += 1              cur = cur.next          k = k % size          if k == 0:  # 不用旋轉              return head          i, pre, newhead = 0, None, head  # pre:newhead的前一個, newhead:新頭部          while i < size - k:              i += 1              pre = newhead              newhead = newhead.next          cur.next = head          pre.next = None          return newhead

問題描述：【Linked List】82. Remove Duplicates from Sorted List II 解題思路：

這道題是給一個鏈表，去除鏈表中重複的元素，只留下原鏈表出現過一次的數字。如 1->2->2->3 變成 1->3。

這道題和下面的 Leetcode 82 思路相同，只不過這道題不需要留下重複的元素。因此除了 Leetcode 82 中的 cur 和 last 外，還需要一個 pre 指向 cur 的前一個位置，便於把所有相同的 cur 全部刪除。 同時，要使用一個標記變數 flag 來記錄連續一段有沒有重複的元素（flag = True），如果沒有重複，只是修改 pre 和 cur 向後各移動一位；否則還要進行指針的交換。注意：比如 [1,2,2,2,2] 這種，循環結束了，但是最後 flag 為 True，因此還需要再進行一次判斷，如果 flag 為 True，要進行一次指針的交換操作。

時間複雜度為 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 deleteDuplicates(self, head: ListNode) -> ListNode:          node = ListNode(-1)          node.next = head          head = node          if not head.next:              return head.next          # cur: 指向第一個重複的元素，last: 工作指針，pre: 是 cur 的前一個位置          pre, cur, last = head, head.next, head.next.next          flag = False          while last:              if cur.val == last.val:                  flag = True                  cur.next = last.next              elif flag:  # 有重複                  pre.next = last                  cur = last                  flag = False    # 不要忘了修改 flag 為 False，標記下一段是否可能有重複              elif not flag:  # 沒有重複                  pre = cur                  cur = last              last = last.next          if flag:  # [1,1]或者[1,2,2]               pre.next = last          return head.next

問題描述：【Linked List】83. Remove Duplicates from Sorted List 解題思路：

這道題是給一個鏈表，去除鏈表中重複的元素。如 1->2->2->3 變成 1->2->3。

只需要兩個指針 cur 和 last，cur 指向相同元素的第一個結點，last 為工作指針，每次向後移動。剩下的就是指針的交換和移動。時間複雜度為 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 deleteDuplicates(self, head: ListNode) -> ListNode:          if not head:              return head          cur, last = head, head.next          while last:              if cur.val == last.val:                  cur.next = last.next              else:                  cur = cur.next              last = last.next          return head

問題描述：【Two Pointers】142. Linked List Cycle II 解題思路：

這道題是給一個鏈表，判斷是否有環。如果有環，找到環的起始位置。

這道題和 Leetcode 【Two Pointers】141. Linked List Cycle 思路一致，都是先使用快慢指針（一個走一步，一個走兩步）判斷是否有環。

對於這道題，如果有環，還要尋找環的起始位置。思路是：定義一個指針 begin 指向鏈表頭，然後和快慢指針的相遇點 slow（或者 fast），每一次都各走一步，直到二者相遇。證明就不寫了，可以參考：LeetCode-142. Linked List Cycle II（詳細證明）與龜兔賽跑演算法的證明過程。

時間複雜度為 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 detectCycle(self, head: ListNode) -> ListNode:          slow = fast = head          flag = True  # 標記是否有環          while fast and fast.next:              slow = slow.next              fast = fast.next.next              if slow == fast:  # 有環                  flag = False                  break          if flag:  # 無環              return None          begin = head          while begin != slow:              begin = begin.next              slow = slow.next          return begin # return slow

問題描述：【Linked List】143. Reorder List 解題思路：

這道題是給一個鏈表，按照 L0→Ln→L1→Ln-1→L2→Ln-2→… 重新排序。

首先第一種想法：遍歷一次鏈表，將各個結點保存到 list 中，按題目順序重新構造鏈表即可。更進一步，我們只需要保存後一半鏈表元素到 list 中，然後將 list 中的元素插入到前半段鏈表中。但是，這樣的操作時間複雜度和空間複雜度均為 O(n)。

有沒有時間複雜度為 O(n)、空間複雜度為 O(1) 的做法？因為後半段需要反過來插入，因此我們可以對後半段鏈表進行反轉，然後再按順序插入到前半段鏈表就行。鏈表反轉可以參考 Leetcode 【Linked List】206. Reverse Linked List。

實際上，當我們遇到需要從尾部操作的鏈表問題（如這道題和 Leetcode 【Linked List】445. Add Two Numbers II），都可以先將鏈表反轉，然後再操作，這樣就不用使用額外空間了。

Python3 實現：

# Definition for singly-linked list.  # class ListNode:  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution:      def reorderList(self, head: ListNode) -> None:          """          Do not return anything, modify head in-place instead.          """          if not head:              return head          l1 = slow = head          fast = head.next          while fast and fast.next:              slow = slow.next              fast = fast.next.next          l2 = self.reverse(slow.next)  # 後半段反轉          slow.next = None  # 斷開前半段          cur1, cur2 = l1, l2          while cur1 and cur2:  # 將後半段依次插入前半段              l2 = l2.next  # 插入              cur2.next = cur1.next              cur1.next = cur2              cur1 = cur2.next  # 移動              cur2 = l2          return l1        def reverse(self, head):          if not head or not head.next:              return head          pre, cur = head, head.next          while cur:              pre.next = cur.next  # 交換              cur.next = head              head = cur              if pre != None:                  cur = pre.next  # 移動          return head

問題描述：【Hash Table】1171. Remove Zero Sum Consecutive Nodes from Linked List 解題思路：

這道題是給一個鏈表，反覆刪去鏈表中總和為 0 的連續結點組成的序列，直到不存在這樣的序列為止。

很明顯這是一道前綴和問題。之前做過前綴和的一個專題：Leetcode【523、525、560、974】，因此需要用到 Hash Table 存儲未出現的前綴和與對應位置的鏈表結點地址。如果再出現相同前綴和，則就刪除兩前綴和地址之間的元素即可（修改指針指向）。

注意： 1、要把 {0: None} 加入到 Hash Table 中，作為前綴和的出口（如 [1,2,-3] 這種情況）。 2、對於鏈表 [1,3,2,-3,-2,5,5,-5,1]，從左到右遍歷，剛開始得到的前綴和分別為 {0: add(None), 1: add(1), 4: add(3), 6: add(2), 3: add(-3)}，當計算到 -2 位置時，前綴和為 3 + (-1) = 1，前綴和 1 之前在 Hash Table 中出現過，因此需要將 add(1) 的下一個地址指向 -2 的下一個地址 add(5)。但是要注意，這時候還要標記 add(1) 後面的前綴和不可用（因為已經被刪除了）。因此，這個時候可以再使用一個集合 discard，用來記錄刪除的那些地址（從 add(1) 的下一個位置開始循環，一直到 add(-2)）。因此，不僅前綴和要在之前出現過，而且前綴和地址不是 discard 中刪除的地址，才可以進行刪除。如果不這樣做，當碰到 add(5) 時，前綴和為 6，又要刪除，從而造成錯誤的結果。

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

Python3 實現：

# Definition for singly-linked list.  # class ListNode:  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution:      def removeZeroSumSublists(self, head: ListNode) -> ListNode:          node = ListNode(-1)          node.next = head          head = node          dic = {0: head}  # 前綴和:地址          discard = set()  # 刪除的地址          presum = 0          cur = head.next          while cur:              presum += cur.val              if presum in dic and dic[presum] not in discard:                  p = dic[presum].next  # 刪除的地址保存在集合中                  while p != cur:                      discard.add(p)                      p = p.next                  dic[presum].next = cur.next  # 指針移動              else:                  dic[presum] = cur              cur = cur.next          return head.next