ゼロから始めるLeetCode Day62「83. Remove Duplicates from Sorted List」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day61「7. Reverse Integer」

次回
まだ

今はTop 100 Liked QuestionsのMediumを優先的に解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。

Twitterやってます。

問題

83. Remove Duplicates from Sorted List

解いた問題と記事を書いた問題の管理が上手くできていなくて、てっきり書いたものだと思っていました。

• ゼロから始めるLeetCode Day48 「26. Remove Duplicates from Sorted Array」

こっちの方しか書いてませんでした。
名前が紛らわしくて思わず笑っちゃいました。

さて、今回の問題ですが、連結リストが与えられるので、全ての要素が一度しか登場しないようにDuplicates(複製)を取り除いてください、という問題です。

Example 1:

Input: 1->1->2
Output: 1->2
Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

解法

僕は以下のように書きました。
他言語特有のん？となるような要素も少ないですし、他の言語で書いていらっしゃる方も読めるのではないでしょうか。

# 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:
        runner = head
        while runner:
            while runner.next and runner.next.val == runner.val:
                runner.next = runner.next.next
            runner = runner.next
        return head
# Runtime: 48 ms, faster than 31.67% of Python3 online submissions for Remove Duplicates from Sorted List.
# Memory Usage: 14 MB, less than 21.02% of Python3 online submissions for Remove Duplicates from Sorted List.

# 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:
        origin = head
        pre = head
        head = None if head is None else head.next
        while head:
            if pre.val == head.val:
                pre.next = head.next
            else:
                pre = pre.next
            head = head.next
        return origin
# Runtime: 44 ms, faster than 58.51% of Python3 online submissions for Remove Duplicates from Sorted List.
# Memory Usage: 13.8 MB, less than 55.82% of Python3 online submissions for Remove Duplicates from Sorted List.        

一方で、二つ保持して書いた方がスピードは出ました。
強いていうなら最初のheadへの代入は内包表記で書いているので一瞬戸惑うかもしれませんね。
要は

if head is None:
    head = None
else:
    head.next

というのを短く書いているだけです。
こうするとreturnとかするときに一個にまとめられるので個人的に好きです。短く楽して書けるの良いですよね。

originを見てたらオリジン弁当が食べたくなってきたので今回はここまで。お疲れ様でした。