Problem
2つのソート済み連結リスト(Linked List) をマージするという問題です。
InputとOutputの例は次になります。
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
What's Linked List?
まず、Pythonでリンクリストを扱うには、通常は専用のクラス（ノードクラス）を定義します。
Leetcodeの問題では、このようなクラスがすでに定義されています。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
一般論として、Linked Listのメリットは、追加・削除などの変更に柔軟に対応できる点、デメリットは目的のデータを見つけるのに１個１個要素を辿る必要があり、データの探索に時間がかかることが上げられます。
Idea
2つのLinkedlistを先頭から一つ一つ比較とポインタの移動を繰り返して行くというのが基本的な考え方になります。
下記のYou tubeの解説がわかりやすいです。
Approach 1 with Iteration
NaïveなIterationだと、下記の様にかけます。
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# 両方のリストが空の場合、空のリストを返す
if not list1 and not list2:
return None
# 一方のリストが空の場合、もう一方のリストを返す
elif not list1:
return list2
elif not list2:
return list1
# リストのヘッドを決定
if list1.val < list2.val:
head = list1
list1 = list1.next
else:
head = list2
list2 = list2.next
# 現在のノードをヘッドに設定
current_node = head
# どちらかのリストが空になるまでループ
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
# どちらかのリストがまだ要素を持っている場合、それを追加
current_node.next = list1 if list1 else list2
return head
このコードでは、list1 と list2 のヘッドを比較してマージされたリストのヘッドを決定し、current_node を用いてそのノードを追跡しています。各ループでは、list1 と list2 のヘッドを比較し、小さい方のノードを current_node.next に設定します。そのノードを追加したリストは次のノードに進みます。これを2つのリストが空になるまで繰り返します。最後に残ったリストがあれば、それを current_node.next に追加します。
このIterationを使った解法では、計算量は下記の様になります。
Time： O(n + m)
- ここで、n と m はそれぞれ list1 と list2 のノード数です。各ノードを1回だけ訪れるため、時間複雑度は O(n + m) となります。
Space： O(1)
- 既存のリストのノードを再利用して新たなリストを作成しており、そのための追加的なスペースはダミーノードと現在のノードを指すポインタ（curr）のみで、これらは一定のスペースしか使用しません。したがって、空間複雑度は O(1) となります。
Approach 2 with Iteration & Dummy node
次に、ダミーノードを利用する方法です。
一般的に、Linkedlistの問題を解くときには、2つのポインターを利用するテクニックが使われます。
dummyは、実際のデータを持たないノードで、OutputとなるLinkedlistの最初の位置を管理します。
具体的には、OutputとなるLinkedlistは、dummy => node1 => node2 => ... と続いています。そのため、
最後には、dummy.nextをreturnします。
ダミーノードにより、edge caseの処理を省略させることができます。Approach 1の冒頭の場合の、リストがnullの場合の処理や、リストのヘッドを決定する処理が不要になっていることがわかります。
def mergeTwoLists(list1, list2):
# ダミーノードを作成
dummy = ListNode()
curr = dummy
# どちらかのリストが空になるまでループ
while list1 and list2:
if list1.val < list2.val:
curr.next = list1
list1 = list1.next
else:
curr.next = list2
list2 = list2.next
curr = curr.next
# どちらかのリストがまだ要素を持っている場合、それを追加
if list1:
curr.next = list1
elif list2:
curr.next = list2
# ダミーノードの次のノードを返す（マージされたリストのヘッド）
return dummy.next
このコードは、ダミーノードにより、新しいリストのヘッドを簡単に追跡できます。ポインタ（ここではcurr）で追跡します。2つのリストのヘッドを比較し、小さい方のノードを新しいリンクリストに追加します。そのノードを追加したリストは次のノードに進みます。これを2つのリストが空になるまで繰り返します。最後に残ったリストがあれば、それを新しいリンクリストの最後に追加します。
Approach 3 with Recursion
下記のコードは、基本的に二つのリストの先頭を比較し、小さい方のノードを選び、その次のノードが二つのリストの残りをマージした結果になるようにしています。このプロセスは再帰的に行われ、ベースケースはリストのいずれかが空になった場合です。このとき、もう一方のリスト全体を返すことで、マージされたリストを得ることができます。
def mergeTwoLists(list1, list2):
# ベースケース: リスト1が空の場合、リスト2を返す
if not list1:
return list2
# ベースケース: リスト2が空の場合、リスト1を返す
elif not list2:
return list1
# 再帰ステップ:
# リスト1の先頭がリスト2の先頭より小さい場合、リスト1の先頭ノードを選び、
# その次のノードがリスト1の残りとリスト2をマージした結果になるようにする
elif list1.val < list2.val:
list1.next = mergeTwoLists(list1.next, list2)
return list1
# リスト2の先頭がリスト1の先頭より小さいか等しい場合、リスト2の先頭ノードを選び、
# その次のノードがリスト1とリスト2の残りをマージした結果になるように
elif list1.val < list2.val:
list1.next = mergeTwoLists(list1.next, list2)
return list1
# リスト2の先頭がリスト1の先頭より小さいか等しい場合、リスト2の先頭ノードを選び、
# その次のノードがリスト1とリスト2の残りをマージした結果になるようにする
else:
list2.next = mergeTwoLists(list1, list2.next)
return list2
この解法では、計算量は下記の様になります。
Time： O(n + m)
- Time complexity の観点では反復的な解法と同等です
Space： O(n + m)
- 再帰呼び出しはスタックを使用します。最悪のケースでは、全てのリンクリストの要素がスタックに積まれる可能性があります。そのため、最悪のケースにおけるSpace complexityは O(n + m) となります。
Reference