RSSフィードを購読
Python Coding Challenge - How will you add two linked lists?
(Python コーディングチャレンジ [超巨大な数値にも対応可能！２つの linked list を足し算しよう！] 編)
(Python コーディングチャレンジ [超巨大な数値にも対応可能！２つの linked list を足し算しよう！] 編)
32 ビットで扱える符号付き数の最大値は 2,147,483,647、64 ビットになると 9,223,372,036,854,775,807 というとんでもなく大きな数字まで扱えます。しかし「宇宙」を相手にしたりするとこれでも「足りない」なんて状況に陥りかねません。でもでも、linked list を利用するとこの壁を乗り越えることが可能になります。
今回は linked list で表した数の足し算を考えます。
問題：
data が 0 から 9 までのいずれかの数字であるノードで構成される２つの linked list が与えられます。１つの liked list は全体で１つの数値を表現しており、LSD (Least Significant Digit: 最下位桁) から並んでいます。
この時、これら２つの linked list を足し算した結果を表す linked list を返すプログラムを記述してください。結果を表す linked list も LSD フォーマットで並んでいなければいけません。また、新たな ListNode を作成しながら繋ぎ合わせていくような方法は認められません。与えられた linked list のポインタを操作して答えを導き出してください。
与えられる２つの linked list はどちらも空ではありませんが、長さが異なる場合があります。
例 1:
Linked list 1: 1 -> 3 -> 5
Linked list 2: 2 -> 4 -> 6
Linked list 2: 2 -> 4 -> 6
# 出力: 3 -> 7 -> 1 -> 1
例 1 の解説:
Linked list 1 は 531 を、linked list 2 は 642 を表しており、合計は 1173 になります。この２つの linked lists を最下位桁から足し算していったものが「出力」されている linked list で、同じく 1173 を表しています。
例 2:
Linked list 1: 9 -> 9 -> 9 -> 9
Linked list 2: 9
Linked list 2: 9
# 出力: 8 -> 0 -> 0 -> 0 -> 1
例 2 の解説:
Linked list 1 は 9999 を、linked list 2 は 9 を表しており、合計は 10008 になります。この２つの linked lists を最下位桁から足し算していったものが「出力」されている linked list で、同じく 10008 を表しています。
１つのノードを表現するクラスは以下の定義を利用します:
from typing import Any, Optional
class ListNode:
def __init__(self, data: Any, next: Optional['ListNode'] = None):
self.data = data
self.next = next
class ListNode:
def __init__(self, data: Any, next: Optional['ListNode'] = None):
self.data = data
self.next = next
また関数定義は以下のような形です (同じである必要はありません):
def add_two_numbers(l1: ListNode, l2: ListNode) -> ListNode:
...
...
考え方:
(まずはこのセクションを読まずに自分で考えてください。またあくまでも「１つの実装アイデア」を提示しているだけです。方法は複数あるはずです。)
通常の linked list はパッと見ていくつのノードが繋がっているのかを判断することはできません。ですから２つの linked list のうちどちらが「長い」のか見分けることができませんから、取り敢えずどちらかの linked list の先頭を head として保存しておき、最終的にこれを答えの先頭ノードとして返すことにします。
また上の例からも分かるように「桁上がり」が生じる可能性があり、その「桁上がり」は次のループ処理で利用することになりますからこれを保存しておくための変数 carry を定義し 0 で初期化しておきます。
それともう１つ、処理が終了したノード (現在処理中の直前のノード) を押さえておくためのポインタ pointer を定義し None で初期化します (この例ではこの pointer で l1 を追っていきます)。これらの変数を使って与えられた２つの linked list の最後のノードまで処理を行なっていきます。
まずは２つの linked list (l1 と l2) の双方が存在する場合のループ処理です。
このループでは、l1 と l2、それと carry を加えたものを total として処理対象とします。この桁に残すべき数値は total % 10、この桁から次の桁への繰り上がりは total // 10 でそれぞれ求めることができます。数値処理が終了したら pointer には現在のノードをセットし、l1 と l2 をそれぞれ次のノードへと進めます。
上のループが終了し、かつ l1 が残っている場合は同様の処理を繰り返していきます。
上のループが終了した時点で l2 が残っている場合は、pointer.next は None としてループから抜けてきていますからこれが l2 を指すように変更しあとは同様の処理を繰り返すことになります。
全てのループを抜けた後に carry が存在している場合は、この値を data とする新しい ListNode を作成し pointer.next にセットしてから head を返します。
２つの linked list を足し算するプログラム実装例：
def add_two_numbers(l1: ListNode, l2: ListNode) -> ListNode:
head = l1
carry = 0
pointer = None
while l1 and l2:
total = l1.data + l2.data + carry
l1.data = total % 10
carry = total // 10
pointer = l1
l1 = l1.next
l2 = l2.next
if l1:
while l1:
total = l1.data + carry
l1.data = total % 10
carry = total // 10
pointer = l1
l1 = l1.next
if l2:
pointer.next = l2
while l2:
total = l2.data + carry
l2.data = total % 10
carry = total // 10
pointer = l2
l2 = l2.next
if carry:
new_node = ListNode(carry)
pointer.next = new_node
return head
res = []
while root:
res.append(str(root.data))
root = root.next
return ' -> '.join(res)
if __name__ == '__main__':
n1_1 = ListNode(1)
n1_2 = ListNode(3)
n1_3 = ListNode(5)
n1_1.next = n1_2
n1_2.next = n1_3
n2_1 = ListNode(2)
n2_2 = ListNode(4)
n2_3 = ListNode(6)
n2_1.next = n2_2
n2_2.next = n2_3
res = add_two_numbers(n1_1, n2_1)
print(make_linked_list_str(res))
head = l1
carry = 0
pointer = None
while l1 and l2:
total = l1.data + l2.data + carry
l1.data = total % 10
carry = total // 10
pointer = l1
l1 = l1.next
l2 = l2.next
if l1:
while l1:
total = l1.data + carry
l1.data = total % 10
carry = total // 10
pointer = l1
l1 = l1.next
if l2:
pointer.next = l2
while l2:
total = l2.data + carry
l2.data = total % 10
carry = total // 10
pointer = l2
l2 = l2.next
if carry:
new_node = ListNode(carry)
pointer.next = new_node
return head
# 与えられた linked list を象徴する文字列を返すヘルパー関数
def make_linked_list_str(root: ListNode) -> str:res = []
while root:
res.append(str(root.data))
root = root.next
return ' -> '.join(res)
if __name__ == '__main__':
n1_1 = ListNode(1)
n1_2 = ListNode(3)
n1_3 = ListNode(5)
n1_1.next = n1_2
n1_2.next = n1_3
n2_1 = ListNode(2)
n2_2 = ListNode(4)
n2_3 = ListNode(6)
n2_1.next = n2_2
n2_2.next = n2_3
res = add_two_numbers(n1_1, n2_1)
print(make_linked_list_str(res))
# 出力: 3 -> 7 -> 1 -> 1
Complexity Analysis
(アルゴリズム解析 - 実行時間解析)
長い方の linked list のノード数が n である場合、ループも合計で n 回繰り返されることになります。よってこのアルゴリズムの時間計算量 (time complexity) は O(n) です。