4. Remove Duplicates from Sorted List II

問題: Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

1 brute force

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        values_to_frequency = {}
        current = head

        while current:
            values_to_frequency[current.val] = values_to_frequency.get(current.val, 0) + 1
            current = current.next
        
        dummy = ListNode()
        last_node_in_removed = dummy

        for value, frequency in values_to_frequency.items():
            if frequency == 1:
                last_node_in_removed.next = ListNode(value)
                last_node_in_removed = last_node_in_removed.next
        
        return dummy.next

ハッシュマップにノードの数字と出現回数を格納して1回だけ出現する数字を見つけてノード作って繋げる。
時間計算量: O(n) 空間計算量: O(n)
実際にといてとか言われたらとりあえずこれ書くかも。

2 オッケーなノードだけ拾って繋げる。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        node_in_removed = dummy
        node_in_original = head

        while node_in_original:
            if node_in_original.next and node_in_original.val == node_in_original.next.val:
                value_to_remove = node_in_original.val
                while node_in_original and node_in_original.val == value_to_remove:
                    node_in_original = node_in_original.next
                continue
            node_in_removed.next = node_in_original
            node_in_removed = node_in_removed.next
            node_in_original = node_in_original.next
        
        node_in_removed.next = None

        return dummy.next

命名がめんどうくさい。
おんなじものをいろんな変数名で参照しても良い

a = [1, 2, 3]
b = a
print(a[1] + a[2])

bにaを代入して初期化したって、aに関する演算には何の影響も及ぼさない。

3 関数に切り出す

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def skip_until_value_change(node, value_to_delete):
            while node and node.val == value_to_delete:
                node = node.next
            return node
        
        dummy = ListNode()
        node_in_removed = dummy
        node_in_original = head

        while node_in_original:
            if node_in_original.next and node_in_original.val == node_in_original.next.val:
                value_to_remove = node_in_original.val
                node_in_original = skip_until_value_change(node_in_original, value_to_remove)
                continue
            node_in_removed.next = node_in_original
            node_in_removed = node_in_removed.next
            node_in_original = node_in_original.next
        
        node_in_removed.next = None
        return dummy.next

4 1重ループ

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        node_in_removed = dummy
        node_in_original = head
        value_to_remove = None

        while node_in_original:
            if node_in_original and node_in_original.val == value_to_remove:
                node_in_original = node_in_original.next
                continue
            if node_in_original.next and node_in_original.val == node_in_original.next.val:
                value_to_remove = node_in_original.val
                continue
            node_in_removed.next = node_in_original
            node_in_removed = node_in_removed.next
            node_in_original = node_in_original.next
        
        node_in_removed.next = None
        return dummy.next