ゼロから始めるLeetCode Day95「82. Remove Duplicates from Sorted List II」

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day94 「929. Unique Email Addresses」

次回
ゼロから始めるLeetCode Day96 「78. Subsets」

Twitterやってます。

問題

82. Remove Duplicates from Sorted List II
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、ソートされた連結リストが与えられた場合、重複した番号を持つすべてのノードを削除し、元のリストとは異なる番号のみを残します。
同様にソートされた連結リストを返します。

Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
Input: 1->1->1->2->3
Output: 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:
        if not head:
            return
        node = pre = ListNode(0)
        node.next = cur = head
        while cur.next:
            nex = cur.next
            if cur.val == nex.val:
                while(nex.next and nex.val == nex.next.val):
                    nex = nex.next
                pre.next = cur = nex.next
                if not cur:
                    return node.next
            else:
                pre,cur,nex = cur,nex,nex.next
        return node.next
# Runtime: 48 ms, faster than 42.22% of Python3 online submissions for Remove Duplicates from Sorted List II.
# Memory Usage: 14 MB, less than 18.49% of Python3 online submissions for Remove Duplicates from Sorted List II.

ランナーをいくつか用意してそれをひたすらずらして仮に一致した場合に異なる要素が出るまでずらし続ける、という方法を取りました。

連結リストは結構パターンが決まっていて解くに連れてすんなりいくことが多くて好きです。
ただ、面接などにおいては単方向か双方向かなどを聞いたり前提条件を整理しておかないとめちゃくちゃになりそうですね。

では今回はここまで。
お疲れ様でした。