Problem overview
Two non-negative integers arrive as linked lists, list1 and list2. Each node holds one digit, and the digits are stored in reverse order: the first node is the ones digit, the second is the tens digit, and so on. The function addTwoNumbers must return their sum as a list in the same format.
For [2, 4, 3] and [5, 6, 4] the numbers are 342 and 465. Their sum is 807, so the result is [7, 0, 8]. The second example, [9,9,9,9,9,9,9] plus [9,9,9,9], is 9999999 + 9999 = 10009998, so the result is [8, 9, 9, 9, 0, 0, 0, 1]. The result is one node longer than either input because of a final carry.
Approach: column addition, digit by digit
The reversed order is a gift. Adding by hand starts at the ones column and moves left, and the lists already begin with the ones digit. So you can add the way you did on paper: take the two digits in a column, add the carry from the previous column, write down the last digit of the total and carry the rest.
The digits never need to be turned into one big number. That matters because the lists can be long, and a number with hundreds of digits doesn't fit in an Int or a Long. Working one column at a time uses only small values.
When one list is shorter, its missing digits count as 0. When both lists are finished but a carry remains, as in the second example, one more digit is added to the result.
Step by step
- Create two cursors,
node1andnode2, asvars starting at the heads. They move as the digits are consumed, and the parameters themselves stay untouched. - Create a dummy head and a
tailcursor. The dummy node is scaffolding: because the result list always starts with a node you make, appending the first digit works the same as appending any other, with no special case.headnever changes, so it is aval.tailmoves, so it is avar. - Start
carryat 0. It holds what overflowed from the previous column. A column's total is at most 9 + 9 + 1 = 19, so the carry is only ever 0 or 1. - Loop while there is anything left to add: a digit in either list, or a carry. The third condition is what produces the extra node at the end of the second example.
- Seed
digitSumwithcarry. This counts the overflow from the previous column first. - Add the digit of each list that still has one, and move that cursor forward. These are two separate
ifstatements, not anif/else, because both lists can contribute to the same column. - Compute the new carry with an
ifexpression: 1 whendigitSumis above 9, otherwise 0. - Reduce
digitSumto one digit with%= 10. - Append a new
ListNodeholding that digit totail.next, then movetailonto it. - Return
head.next. The dummy node holds a placeholder 0 and isn't part of the answer.
The solution in Kotlin
class Solution {
fun 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!!
}
return head.next
}
}
The Kotlin details worth knowing:
- Backticks around
val.valis a keyword, but the node's field has that name, so it is writtennode1.`val`. Backticks let a keyword be used as an ordinary name. - Smart casts. After
if (node1 != null), Kotlin treats the localvar node1as a non-nullListNodeinside the block, sonode1.`val`needs no?.or!!. This works becausenode1is a local variable that nothing else can change in between. tail.next!!. The propertynextis declaredListNode?, whiletailis a non-nullListNode. Kotlin doesn't remember that the line above just assigned a node, so!!asserts that it isn'tnull. It would throw if it were, but here it never is.ifas an expression. Kotlin has no ternary operator.if (digitSum > 9) 1 else 0is an expression that yields a value, so it can sit on the right of=.- Semicolons. They are optional in Kotlin, but a semicolon lets two statements share a line, as in
var node1 = list1; var node2 = list2. ListNode()with no argument creates the dummy node with the default digit 0.
Complexity
Time: O(max(m, n)), where m and n are the lengths of the lists. The loop runs once per column, which is the length of the longer list, plus at most one extra time for a final carry. Each iteration does a constant amount of work.
Space: O(max(m, n)) for the result, which has one node per output digit. Apart from the result, only a few variables are used.
Edge cases and common mistakes
- Lists of different lengths.
[1, 8]plus[0]gives[1, 8]. Oncenode2isnull, the secondifis skipped, which is the same as adding 0. - A final carry.
[5]plus[5]gives[0, 1]. Withoutcarry > 0in the loop condition, the leading 1 would be lost. - Zero.
[0]plus[0]gives[0], a single node. The loop runs once because both lists have a digit. - Using
elsefor the second list. This skips digits whenever both lists have one. - Returning
head. That includes the dummy 0 at the front, which makes the sum ten times too big. - Converting to numbers. A list of 30 nines overflows both
IntandLong. Column addition has no such limit. - Writing the digits in the wrong order. The result must also have the ones digit first, so each new digit goes at the end of the list.
Testing
[2, 4, 3]and[5, 6, 4]gives[7, 0, 8].[9, 9, 9, 9, 9, 9, 9]and[9, 9, 9, 9]gives[8, 9, 9, 9, 0, 0, 0, 1].[0]and[0]gives[0].[5]and[5]gives[0, 1].[1, 8]and[0]gives[1, 8].