EMP Tech BlogPublicationへの投稿
💡

ゼロから始めるLeetCode Day13「21. Merge Two Sorted Lists」

take6
に公開
LeetCode
tech

概要

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

その対策としてLeetCodeなるサイトで対策を行うようです。

※LeetCodeとは
本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトです。

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

LeetCode

問題

21. Merge Two Sorted Lists

与えられた2つのソート済みリンクリストlist1とlist2を入力として受け取り、これら2つのリストを1つのソートされたリストに統合する関数を作成する問題。

Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:
Input: list1 = [], list2 = []
Output: []

Example 3:
Input: list1 = [], list2 = [0]
Output: [0]

Constraints:
・The number of nodes in both lists is in the range [0, 50].
・-100 <= Node.val <= 100
・Both list1 and list2 are sorted in non-decreasing order.

解法

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode()
        current = dummy_head

        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next

        if list1:
            current.next = list1
        elif list2:
            current.next = list2

        return dummy_head.next

空のリストを用意する

dummy_head = ListNode()
current = dummy_head

dummy_head = ListNode()
マージされたリストの先頭に、値を持たない一時的なノードを作成する。

current = dummy_head
currentポインタは、現在構築中のマージされたリストの末尾を追跡するために使用される。

リストの比較と結合

while list1 and list2:
    if list1.val <= list2.val:
        current.next = list1
        list1 = list1.next
    else:
        current.next = list2
        list2 = list2.next
    current = current.next

if list1.val <= list2.val:
list1の値がlist2の値以下であれば、
current.next = list1
list1の現在のノードをマージされたリストの次（current.next）に追加する。
list1 = list1.next
list1ポインタを次のノードに進める。

else
もし、list2の値の方が小さい（または等しい）場合
current.next = list2
list2 の現在のノードをマージされたリストの次（current.next）に追加する。
list2 = list2.next
list2ポインタを次のノードに進める。

current = current.next
currentポインタを新しく追加されたノード（つまり、マージされたリストの新しい末尾）に進める。

残りのノードの処理

if list1:
    current.next = list1
elif list2:
    current.next = list2

while ループが終了したとき、list1またはlist2のどちらか一方（あるいは両方）が None になっている。
この部分では、残っている方のリストのノードを、マージされたリスト（current.next）の末尾にすべて追加する。

結果の返却

return dummy_head.next

dummy_head.nextが、マージされたリストの最初のノードになるので、これを返す。

例

Input: list1 = [1,2,4], list2 = [1,3,4]

list1 / list2 の現在のノード List1.val <= list2.val マージされたリストの進捗 (dummy_head.next)
list1: 1, list2: 1 True。　list1の1を選択 1
list1: 2, list2: 1 False。　list2の1を選択 1 -> 1
list1: 2, list2: 3 True。　list1の2を選択 1 -> 1 -> 2
list1: 4, list2: 3 False。　list2の3を選択 1 -> 1 -> 2 -> 3
list1: 4, list2: 4 True。 list1の4を選択 1 -> 1 -> 2 -> 3 -> 4
list1: None, list2: 4 list1が空になったため、残りのlist2のノードをすべて追加。 1 -> 1 -> 2 -> 3 -> 4 -> 4

最終的に、dummy_head.nextは 1-> 1 -> 2 -> 3 -> 4 -> 4となる

EMP Tech Blog
EMP Tech BlogPublication

インフラをメインに、IoTやAI、自動化などの最先端分野のプロジェクトに取り組む少数精鋭エンジニア集団、株式会社EmpireのTech Blogです！

Discussion