【LeetCode】82. Remove Duplicates from Sorted List II 解答・解説【Python】

問題
1. 原文
2. 内容
方針
解答
1. 解答1：
2. 解答2
補足・参考・感想

問題

原文

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.

Example 1:

Input: head = [1,2,3,3,4,4,5] Output: [1,2,5]

1
2

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3] Output: [2,3]

1
2

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

The number of nodes in the list is in the range [0, 300].

-100 <= Node.val <= 100

The list is guaranteed to be sorted in ascending order.

内容

ソートされた連結リストheadが与えられるので、重複する全ノードを削除し、相異なる数字のみ残してください。同様にソートして返してください。

制約

・リスト内のノード数は0~300

・ノードの値は-100~100

・リストは昇順ソートが保証されている

※正しくない可能性があります。

方針

・ハッシュテーブルで各要素の出現回数が1のみ拾って返す

解答

解答1：

# 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: Optional[ListNode]) -> Optional[ListNode]:
        tmp = ListNode(0)
        ans = tmp
        a = []
        dic = {}
        #headを一巡してリストaに全要素を追加
        while head:
            a.append(head.val)
            head = head.next
        #
        for i in a:
            #aの各要素をキーとして、aに出てきた数だけ値に1を加える
            dic[i] = dic.get(i,0) + 1
        #出現回数が1の要素だけはansに加えて連結リストにして返す。
        for k in dic.keys():
            if dic[k]==1:
                ans.next = ListNode(k)
                ans = ans.next
        return tmp.next

# 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: Optional[ListNode]) -> Optional[ListNode]:

tmp = ListNode(0)

ans = tmp

a = []

dic = {}

#headを一巡してリストaに全要素を追加

while head:

a.append(head.val)

head = head.next

for i in a:

#aの各要素をキーとして、aに出てきた数だけ値に1を加える

dic[i] = dic.get(i,0) + 1

#出現回数が1の要素だけはansに加えて連結リストにして返す。

for k in dic.keys():

if dic[k]==1:

ans.next = ListNode(k)

ans = ans.next

return tmp.next

・一度連結リストからリストaに全要素を保持

・リストaの各要素をキーとして、その出現回数を値として辞書dicに保持

・出現回数が1(dicの値が1)の要素を連結リストにして返す

解答2

補足・参考・感想

参考

前：61. Rotate List

次：114. Flatten Binary Tree to Linked List

LeetCode 解答・解説記事一覧