LeetCode 4452つの数字を追加II

Leetcode 445 Add Two Numbers Ii

LeetCode 4452つの数字を追加II

2つの非負の整数を表すために、2つの空でないリンクリストが指定されています。番号の最上位桁はリストの先頭にあります。各ノードには、1つの番号のみが格納されます。これらの2つの数値を追加すると、新しいリンクリストが返されます。

数値0を除いて、これらの数値はどちらもゼロで始まらないと想定できます。

上級：

入力リストを変更できない場合はどうすればよいですか？つまり、リスト内のノードを反転することはできません。

例：

Enter: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7

思考分析

計算中に右端の数値の配置が保証されるため、スタックを使用して各値をリンクリストに格納し、順番に計算することを考えるのが自然です。追加時にキャリーが生成される可能性があるため、キャリーがあるかどうかを示すフラグが使用されます。

ヒント：スタックに要素を追加した後もキャリーが残っている場合は、新しいヘッドノードを追加する必要があります。

迅速なソリューション

public class ListNode { public var val: Int public var next: ListNode? public init(_ val: Int) { self.val = val self.next = nil } } class Solution { func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? { var node1 = l1 var node2 = l2 var stack1 = [Int]() var stack2 = [Int]() while node1 != nil { stack1.append(node1!.val) node1 = node1!.next } while node2 != nil { stack2.append(node2!.val) node2 = node2!.next } var flag = 0 var head: ListNode? = nil while stack1.count > 0 || stack2.count > 0 || flag > 0 { if stack1.count > 0 { flag += stack1.popLast()! } if stack2.count > 0 { flag += stack2.popLast()! } let node: ListNode = ListNode(flag % 10) node.next = head head = node flag = flag / 10 } return head } }