📌
よわよわエンジニアが解くLeetcode 21. Merge Two Sorted Lists
主に顧客折衝メインの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