📌

よわよわエンジニアが解くLeetcode 21. Merge Two Sorted Lists

2024/03/16に公開

主に顧客折衝メインのSIerに10年いましたが、Web系エンジニアになるためにアルゴリズムを勉強しております。
ゼロから勉強しているので、一部の人のためになればと思い、学んだことを共有します。

連結リストとは、一連のノード(または要素)がチェーンのように連なって構成されるデータ構造です。各ノードは、それ自体が持つデータ(この例では数値0, 1, 3, 4など)と、リスト内の次のノードへの参照(ポインタ)を含んでいます。この参照によって、リストの次の要素が何であるか(次に指し示す値が何であるか)がわかります。

[0] -> [1] -> [3] -> [4] -> None

以下は実装と、わからなかったことのメモです。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# ダミーは最後まで先頭にいる。カレントは常に最新のノードを指し示す。
dummy_node = ListNode()
current_node = dummy_node

while list1 and list2:
    # 連結リストには値とポインタが含まれる
    if list1.val <= list2.val:
        current_node.next = list1
        list1 = list1.next
    else:
        current_node.next = list2
        list2 = list2.next
    # カレントを追加したノードに更新する
    current_node = current_node.next

if list1:
    # list1には次の全リストの情報が含まれる
    current_node.next = list1
else:
    current_node.next = list2

# ダミーの次から返却する
return dummy_node.next

Discussion