This page looks best with JavaScript enabled

Leetcode 82 Remove Duplicates from Sorted List II

題目大意

  • 給一個已經按照 val 排序過的 linked list, 刪除所有 value 有重複的 node 之後,再回傳 linked list
  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100

Problem

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

My Solution

第一版

  • 因為第一個 node 不一定沒有重複,所以在最前面裝上一個假的 node
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        head = node = re = ListNode(None, head)
        while head.next and head.next.next:
            if head.val != head.next.val != head.next.next.val:
                node.next = head.next
                node = node.next
            head = head.next
        print(head)
        if head.next and head.val != head.next.val:
            node.next = head.next
        else:
            node.next = None
        return re.next
  • 在最前面裝上假的 node 之後, head, node 兩個指標都先指著假開頭,而 re 則是存好假開頭,把答案存放在他的後面
  • 每次判斷都會使用到相鄰的三個 node, 分別為: (head, head.next, head.next.next)
  • 因為輸入的 linked list 排序過,所以判斷方式為: 只有中間的 node 與兩側 value 不相同才保留該 node
  • 當 while 迴圈執行完,(head, head.next, head.next.next) 指著 (XXX, YYY, None),所以還要判斷 YYY 是否要留下
  • 最後回傳 re.next

第二版 小改良

把上面作法的判斷最後非空的兩個 node 合併一起處理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        prev = node = re = ListNode(None, head)
        while head:
            if prev.val != head.val and (not head.next or head.val != head.next.val):
            # 也就是合併過的: if (prev.val != head.val and not head.next) or (prev.val != head.val != head.next.val)
                node.next = head
                node = node.next
            prev = prev.next
            head = head.next
        node.next = None
        return re.next
  • 一樣前面裝上假 node, 使用兩個指標 prev, node, 判斷方式同上,也是 (prev, head, head.next) 中間的 node 與兩側不同才保留
  • if 判斷改為: 如果中間與兩側不同 或是最右邊碰到 None。此時會存下中間的 head
  • 然後將兩個指標向右移動
  • 當沒有 node 可以操作,結尾裝上空 node 然後回傳答案