検索ガイド -Search Guide-

単語と単語を空白で区切ることで AND 検索になります。
例: python デコレータ ('python' と 'デコレータ' 両方を含む記事を検索します)
単語の前に '-' を付けることで NOT 検索になります。
例: python -デコレータ ('python' は含むが 'デコレータ' は含まない記事を検索します)
" (ダブルクオート) で語句を囲むことで 完全一致検索になります。
例: "python data" 実装 ('python data' と '実装' 両方を含む記事を検索します。'python data 実装' の検索とは異なります。)
python_coding_challenge

Python coding challenge - 超巨大な数値にも対応可能!2つの linked list を足し算しよう! 投稿一覧へ戻る

Published 2022年7月24日9:24 by mootaro23

SUPPORT UKRAINE

- Your indifference to the act of cruelty can thrive rogue nations like Russia -

Python Coding Challenge - How will you add two linked lists?
(Python コーディングチャレンジ [超巨大な数値にも対応可能!2つの linked list を足し算しよう!] 編)

32 ビットで扱える符号付き数の最大値は 2,147,483,647、64 ビットになると 9,223,372,036,854,775,807 というとんでもなく大きな数字まで扱えます。しかし「宇宙」を相手にしたりするとこれでも「足りない」なんて状況に陥りかねません。でもでも、linked list を利用するとこの壁を乗り越えることが可能になります。
今回は linked list で表した数の足し算を考えます。
問題:
data が 0 から 9 までのいずれかの数字であるノードで構成される2つの linked list が与えられます。1つの liked list は全体で1つの数値を表現しており、LSD (Least Significant Digit: 最下位桁) から並んでいます。
この時、これら2つの linked list を足し算した結果を表す linked list を返すプログラムを記述してください。結果を表す linked list も LSD フォーマットで並んでいなければいけません。また、新たな ListNode を作成しながら繋ぎ合わせていくような方法は認められません。与えられた linked list のポインタを操作して答えを導き出してください。
与えられる2つの linked list はどちらも空ではありませんが、長さが異なる場合があります。
例 1:
Linked list 1: 1 -> 3 -> 5
Linked list 2: 2 -> 4 -> 6

# 出力: 3 -> 7 -> 1 -> 1
例 1 の解説:
Linked list 1 は 531 を、linked list 2 は 642 を表しており、合計は 1173 になります。この2つの linked lists を最下位桁から足し算していったものが「出力」されている linked list で、同じく 1173 を表しています。
例 2:
Linked list 1: 9 -> 9 -> 9 -> 9
Linked list 2: 9

# 出力: 8 -> 0 -> 0 -> 0 -> 1
例 2 の解説:
Linked list 1 は 9999 を、linked list 2 は 9 を表しており、合計は 10008 になります。この2つの linked lists を最下位桁から足し算していったものが「出力」されている linked list で、同じく 10008 を表しています。
1つのノードを表現するクラスは以下の定義を利用します:
from typing import Any, Optional


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:
...
考え方:
(まずはこのセクションを読まずに自分で考えてください。またあくまでも「1つの実装アイデア」を提示しているだけです。方法は複数あるはずです。)
通常の linked list はパッと見ていくつのノードが繋がっているのかを判断することはできません。ですから2つの linked list のうちどちらが「長い」のか見分けることができませんから、取り敢えずどちらかの linked list の先頭を head として保存しておき、最終的にこれを答えの先頭ノードとして返すことにします。
また上の例からも分かるように「桁上がり」が生じる可能性があり、その「桁上がり」は次のループ処理で利用することになりますからこれを保存しておくための変数 carry を定義し 0 で初期化しておきます。
それともう1つ、処理が終了したノード (現在処理中の直前のノード) を押さえておくためのポインタ pointer を定義し None で初期化します (この例ではこの pointer で l1 を追っていきます)。これらの変数を使って与えられた2つの linked list の最後のノードまで処理を行なっていきます。
まずは2つの 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 を返します。
2つの 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

# 与えられた 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) です。