問題
原文
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Example 2:
Example 3:
Constraints:
- The number of nodes in each linked list is in the range
[1, 100].0 <= Node.val <= 9- It is guaranteed that the list represents a number that does not have leading zeros.
内容
2つの空ではなく非負整数を含む連結リストが与えられます。数字は逆順で入れられており、各ノードは一桁の数字を含みます。2つの数字を加え、その合計を連結リストとして返してください。
先頭が0から始まる数字はないと仮定して良いです。※0を除く
以下補足です。
テストケースを見る限り、2つの連結リストが与えられるので、1つの数字として結合し、逆順に並べ替えた上で数字として足し算し、その結果を再度逆順に並べ替えして、連結リストとして返す必要があります。
list1 = [1,2,3] →321
list2 = [4,5,6] →654
321+654 = 975 →579
579を連結リストとして返すというイメージです。
※正しくない可能性があります。
方針
・解答1
→2つの連結リストを結合して逆順に変換して加算し、文字列に戻し、加算結果を逆順にする。
→上記により得た文字列を要素ごとに連結リストの各ノードとして作成して返す
解答
解答1：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: #リスト内の各要素を文字列として結合 #n1とn2を文字列として用意 n1 = "" n2 = "" #l1の要素がある限り各要素を文字列としてn1に代入 while l1 is not None: n1 += str(l1.val) #次のノードへ移ります。l1.nextはListNodeクラスの属性(解答欄の一番上にコメントアウトで定義されています) l1 = l1.next #l2の各要素を文字列としてn2に代入 while l2 is not None: n2 += str(l2.val) #次のノードへ移ります。l2.nextはListNodeクラスの属性(解答欄の一番上にコメントアウトで定義されています) l2 = l2.next #n1:243, n2:564が上記操作の結果(テストケース1の場合) #n1,n2を反転 n1 = n1[::-1] n2 = n2[::-1] #intで加算して再度strに戻す ans_str = str(int(n1)+int(n2)) #答えを反転 ans_str = ans_str[::-1] #以降はlinked listへの変換 #ans,travをインスタンス化 #どちらもインスタンス化の際、属性としてval=0,next=Noneを持つ ans = trav = ListNode() #ans_strの文字数分だけ処理(連結リストのノードを作成していく) for i in range(len(ans_str)): #i番目の要素をvalに格納 trav.val = ans_str[i] #終端でない場合はtrav.nextを再度インスタンス化 if i != len(ans_str) -1: trav.next = ListNode() #終端の場合はtrav.next(None)が入る？ trav = trav.next return ans |
補足・参考・感想
参考
コメント