Problem overview
The method addTwoNumbers receives two non-empty linked lists, list1 and list2. Each list stores a non-negative integer with one digit per node, in reverse order: the first node is the ones digit, the next is the tens digit, and so on. The method returns their sum as a new list in the same format. Neither number has leading zeros, except for the number 0 itself.
In the first example, [2, 4, 3] is 342 and [5, 6, 4] is 465, and 342 + 465 = 807, so the result is [7, 0, 8]. In the second, [9, 9, 9, 9, 9, 9, 9] is 9999999 and [9, 9, 9, 9] is 9999. The sum is 10009998, which is the list [8, 9, 9, 9, 0, 0, 0, 1]. The result is one node longer than the longer input, because a carry spilled out of the last column.
Approach: the column addition you learned at school
You can't convert the lists to integers and add them: the numbers can have far more digits than an Int or a Long holds. Instead, add the way you do on paper, one column at a time, starting from the ones.
The reversed order is what makes this convenient. The first node of each list is already the least significant digit, so walking from the heads visits the columns in the order you need. For each column, add the two digits and the carry from the previous column. The digit to store is the sum modulo 10, and the new carry is 1 if the sum went past 9, otherwise 0. The largest possible column sum is 9 + 9 + 1 = 19, so the carry is never more than 1.
Two details need care. One list may be shorter, so a missing digit counts as 0. And when both lists are used up, a final carry of 1 still needs a node of its own.
Step by step
- Create two cursors,
node1andnode2, starting at the two heads. They arevars because they move, and the parameters themselves can't be reassigned. Scala allows two statements on one line when a semicolon separates them. - Create a dummy node
headand a cursortailthat starts on it. The result is built after the dummy, so appending the first digit needs no special case.headnever changes, so it is aval;tailmoves, so it is avar. - Start the carry at 0.
- Loop while either list has digits left or the carry is positive:
node1 != null || node2 != null || carry > 0. The last condition keeps the final carry from being lost. Scala conditions must beBoolean, so the comparisons are written out. - Seed the column sum:
var digitSum = carry. - Add the first list's digit if
node1is notnull, and advancenode1. The field is`val`in backticks, becausevalis a Scala keyword. - Do the same for the second list with a separate
if, not anelse, since both lists can have a digit in the same column. - Compute the new carry:
carry = if (digitSum > 9) 1 else 0. - Reduce the sum to one digit with
digitSum %= 10. - Append a node holding
digitSum:tail.next = ListNode(digitSum). - Move
tailonto the new node, so the next digit goes after it instead of replacing it. - Return
head.next, skipping the dummy.
The solution in Scala
class Solution {
def addTwoNumbers(list1: ListNode, list2: ListNode): ListNode = {
var node1 = list1; var node2 = list2
val head = ListNode(); var tail = head
var carry = 0
while (node1 != null || node2 != null || carry > 0) {
var digitSum = carry
if (node1 != null) {
digitSum += node1.`val`
node1 = node1.next
}
if (node2 != null) {
digitSum += node2.`val`
node2 = node2.next
}
carry = if (digitSum > 9) 1 else 0
digitSum %= 10
tail.next = ListNode(digitSum)
tail = tail.next
}
head.next
}
}
The Scala details worth knowing:
- Backticks around
val. A keyword can still be used as a name if it is wrapped in backticks, sonode1.`val`reads the field calledval. Without the backticks the code doesn't parse. ifis an expression. Scala has no ternary operator, butif (digitSum > 9) 1 else 0produces a value, so it can sit on the right of an assignment.- Compound assignment.
digitSum += xanddigitSum %= 10update avarin place.%is the remainder operator, so19 % 10is 9. - Creating nodes without
new. The lesson's code writesListNode()andListNode(digitSum). Scala 3 allows calling a class like a function, sonewis optional. - The last expression is the result.
head.nexthas noreturnin front of it, and that is the normal Scala style. valversusvarforheadandtail. Aftervar tail = head, the two names refer to the same node, but onlytailcan be pointed at a different node later. Changingtail.nextmodifies the shared dummy node, which is how the result list gets attached tohead.
Complexity
Time: O(max(m, n)), where m and n are the lengths of the two lists. The loop runs once per column, which is the longer length, plus one more time at most for a final carry.
Space: O(max(m, n)) for the output list, since it needs one node per digit of the sum. Apart from that output, the extra memory is a few variables.
Edge cases and common mistakes
- A final carry.
[5]plus[5]is[0, 1]. Withoutcarry > 0in the loop condition, the 1 would be dropped and the answer would be[0]. - Lists of different lengths.
[1, 8]plus[0]is[1, 8]. Eachifchecks its own cursor, so the shorter list contributes nothing once it ends. - Using
elsefor the second list. Then only one list would be added per column and the sums would be wrong. - Forgetting to advance
tail. Every new digit would overwrite the previous node'snext, and the result would contain only the last digit. - Returning
head. That includes the dummy node and adds a stray 0 at the front. - Carrying more than 1. Using
digitSum / 10also works, since the carry can only be 0 or 1. The comparison is simply a more explicit way to say the same thing. - Zero.
[0]plus[0]gives[0]: the loop runs once, because both cursors start non-null, and it appends a single 0.
Testing
[2, 4, 3]and[5, 6, 4]give[7, 0, 8].[9, 9, 9, 9, 9, 9, 9]and[9, 9, 9, 9]give[8, 9, 9, 9, 0, 0, 0, 1].[0]and[0]give[0].[5]and[5]give[0, 1].[1, 8]and[0]give[1, 8].
