[leetcode] 445.2つの数字を追加II @ python



445 Add Two Numbers Ii Python



元の質問

2つの非負の整数を表す2つの空でないリンクリストが与えられます。最上位桁が最初に来て、それらの各ノードには1桁が含まれます。 2つの数値を加算し、リンクリストとして返します。

2つの数値には、数値0自体を除いて、先行ゼロが含まれていないと想定できます。



ファローアップ:
入力リストを変更できない場合はどうなりますか?つまり、リストを逆にすることはできません。

例:



入力:(7-> 2-> 4-> 3)+(5-> 6-> 4)
出力:7-> 8-> 0-> 7

解決

最初にgetNum関数を定義してリンクリストを整数に変換し、次に2つの整数を追加し、結果を数値のリストに変換し、ダミーノードを作成し、リストをトラバースし、リストから最初の数値を毎回抽出します。ノードの次のノード、最後にdummy.nextを返します
時間:O(L1)+ O(L2)+ O(L1 + L2)、L1はl1の長さ、L1 + L2はl1とl2の長さ
スペース:O(1)

コード

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def addTwoNumbers(self, l1, l2): ''' :type l1: ListNode :type l2: ListNode :rtype: ListNode ''' res = self.getNum(l1) + self.getNum(l2) res = [int(char) for char in list(str(res))] # convert res to linked list dummy = p = ListNode(0) while res: p.next = ListNode(res.pop(0)) p = p.next return dummy.next def getNum(self, node): l = [] while node: l.append(str(node.val)) node = node.next return int(''.join(l))