Problem overview
The method addTwoNumbers receives two non-empty linked lists, list1 and list2. Each list is a non-negative integer with one digit per node, stored in reverse order: the first node holds the ones digit, the next the tens digit, and so on. The method returns their sum as a list in the same format. The numbers have no leading zeros, except for the number 0 itself.
In the first example, [2, 4, 3] is 342 and [5, 6, 4] is 465. Their sum is 807, so the result is [7, 0, 8]. In the second example, [9, 9, 9, 9, 9, 9, 9] plus [9, 9, 9, 9] is 10,009,998, which comes back as [8, 9, 9, 9, 0, 0, 0, 1]: the result has one more digit than the longer input.
Approach: do it the way you add on paper
Reverse order is convenient. Written addition starts with the ones column and moves left, and the lists already start with the ones digit. So the code can walk both lists from the head, add one column at a time, and build the result from its least significant digit, which is also the order the answer needs.
For each column, the sum is the digit of the first list, plus the digit of the second list, plus the carry from the previous column. A list that has run out contributes 0. The new digit is that sum modulo 10, and the new carry is 1 if the sum is above 9, otherwise 0. The largest possible column sum is 9 + 9 + 1 = 19, so the carry is never more than 1.
The loop must continue while either list has digits left or there is a carry. The carry condition is what produces the extra digit at the end, as in 5 + 5, which is [0, 1].
Converting the lists to numbers and adding them is a trap. Lists can be long enough that the value doesn't fit in an Int, which has 64 bits in Swift, so working column by column is the safe approach.
Step by step
- Create the cursors.
node1andnode2start at the two heads. They arevar, because they move. Swift lets onevardeclare both, separated by a comma. - Create a dummy head
head, and atailthat starts on it. The dummy removes the special case for the first result node.headnever changes, so it is alet, andtailmoves, so it is avar. - Start the carry at 0. The first column has no carry coming in.
- Loop while there is work. The condition is
node1 != nil || node2 != nil || carry > 0. Swift conditions must beBool, so each part is an explicit comparison. - Seed the column sum with the carry:
var digitSum = carry. - Take a digit from the first list if there is one. Add
node1!.valand movenode1to itsnext. The!is safe because theifjust checked fornil. - Do the same for the second list with a separate
if, not anelse. Both lists can have a digit in the same column. - Compute the carry with a ternary:
digitSum > 9 ? 1 : 0. - Reduce the sum to one digit with
digitSum %= 10. - Append a node holding the digit to
tail.next, then movetailonto it. - Return
head.next, skipping the dummy, which holds a meaningless 0.
The solution in Swift
class Solution {
func addTwoNumbers(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
var node1 = list1, node2 = list2
let head = ListNode(); var tail = head
var carry = 0
while node1 != nil || node2 != nil || carry > 0 {
var digitSum = carry
if node1 != nil {
digitSum += node1!.val
node1 = node1!.next
}
if node2 != nil {
digitSum += node2!.val
node2 = node2!.next
}
carry = digitSum > 9 ? 1 : 0
digitSum %= 10
tail.next = ListNode(digitSum)
tail = tail.next!
}
return head.next
}
}
Swift details worth knowing:
- A
Boolis not anInt. In Swift,carry = digitSum > 9doesn't compile: the compiler says it cannot assign a value of typeBoolto typeInt. The ternary? 1 : 0converts the comparison into a number. let head = ListNode()and thentail.next = ....letmakes the variable constant, not the object.ListNodeis a class, soheadcan't be reassigned, but its properties can change.tailstarts as the same object and is reassigned as it moves.- Two optionals, two unwraps.
node1is aListNode?. After thenilcheck the code still writesnode1!, because Swift doesn't narrow the type of avarin this style of check.tail.nextis also optional, sotail = tail.next!is needed even though the line above just assigned it. %=. It replaces the variable with the remainder after division by 10.12 % 10is 2, and8 % 10is 8.- Overflow traps in Swift. Integer arithmetic that overflows
Intcrashes the program instead of wrapping. The column sums here stay at 19 or less, so the code never gets close, but a conversion of long lists to one bigIntwould crash.
Complexity
Let m and n be the lengths of the lists.
Time: O(max(m, n)). Each loop iteration consumes one digit from at least one list, or handles the last carry, and each iteration costs constant time.
Space: O(max(m, n)) for the result. The new list has at most max(m, n) + 1 nodes. Apart from the output, the code uses only a few variables, and it leaves the input lists unchanged.
Edge cases and common mistakes
- Different lengths. For
[1]and[9, 9](1 + 99) the result is[0, 0, 1]. The shorter list simply stops contributing. - A final carry.
[5]plus[5]gives[0, 1]. Withoutcarry > 0in the loop condition, the last 1 would be dropped. - Zeros.
[0]plus[0]gives[0]. The loop runs once for the single column, produces 0, and then stops because there is no carry. - Using
elsefor the second list. Then each column would take a digit from only one list, and the sums would be wrong. - Returning
head. The dummy's 0 would show up as an extra leading node. Returnhead.next.
Testing
[2, 4, 3]and[5, 6, 4]give[7, 0, 8].[0]and[0]give[0].[9, 9, 9, 9, 9, 9, 9]and[9, 9, 9, 9]give[8, 9, 9, 9, 0, 0, 0, 1].[5]and[5]give[0, 1].[1]and[9, 9]give[0, 0, 1].
