Problem overview
The method addTwoNumbers receives two non-empty linked lists, list1 and list2. Each represents a non-negative integer with one digit per node, and the digits are stored in reverse order: the head holds the ones digit, the next node the tens digit, and so on. The method must return the sum in the same format, as a new linked list.
In the first example, [2, 4, 3] is the number 342 and [5, 6, 4] is 465. Their sum, 807, is returned as [7, 0, 8]. In the second, [9, 9, 9, 9, 9, 9, 9] plus [9, 9, 9, 9] is 9999999 + 9999 = 10009998, returned as [8, 9, 9, 9, 0, 0, 0, 1]. The result is one digit longer than the longer input.
Approach: do what you do on paper
You add numbers on paper from the right, digit by digit, writing the ones digit and carrying the rest. The reverse order of the lists makes this convenient: the head of each list is already the rightmost column, so one pass from the heads does the whole job.
Converting each list to a number, adding, and converting back looks tempting, but it breaks. In TypeScript, number is a 64-bit floating-point value, and integers above 2**53 lose precision. A list can hold far more digits than that allows. Adding column by column never builds a big number, so it works for any length.
For each column, compute digitSum = digit1 + digit2 + carry. The new digit is digitSum % 10 and the new carry is 1 when digitSum is above 9, otherwise 0. The largest possible column is 9 + 9 + 1 = 19, so the carry never exceeds 1.
Two details make the loop simple:
- When one list is shorter, its missing digits count as 0, so each list is read only while it still has nodes.
- The loop continues while either list has digits or a carry is left. That is what produces the extra leading 1 in
9999999 + 9999.
Step by step
- Create the cursors
node1andnode2at the two heads. Moving them leaves the parameters untouched. - Build a dummy head and a
tailthat starts on it. Every new digit is appended aftertail, so the first digit needs no special case. The dummy's own value is never returned. - Start
carryat 0. There is nothing to carry into the first column. - Loop while any of the three is truthy:
node1,node2orcarry. A node is truthy andnullis falsy, andcarryis truthy when it is 1. - Seed
digitSumwithcarry. Declared inside the loop, it starts fresh for every column. - Add the digit of
node1if it exists, then movenode1to the next node. - Do the same for
node2with a separateif. Anelsewould be wrong, because both lists can contribute to the same column. - Update the carry with a ternary. The comparison
digitSum > 9is a boolean, and TypeScript won't accept a boolean in anumbervariable, so? 1 : 0turns it into a number. - Reduce
digitSumto one digit with%= 10. - Append a new node holding the digit to
tail.next, then movetailonto it so the next digit follows rather than replaces it. - Return
head.next, skipping the dummy.
The solution in TypeScript
class Solution {
addTwoNumbers(list1: ListNode | null, list2: ListNode | null): ListNode | null {
let node1 = list1, node2 = list2;
let head = new ListNode(), tail = head;
let carry = 0;
while (node1 || node2 || carry) {
let digitSum = carry;
if (node1) {
digitSum += node1.val;
node1 = node1.next;
}
if (node2) {
digitSum += node2.val;
node2 = node2.next;
}
carry = digitSum > 9 ? 1 : 0;
digitSum %= 10;
tail.next = new ListNode(digitSum);
tail = tail.next;
}
return head.next;
}
}
The TypeScript details worth knowing:
- Inferred types.
let carry = 0givescarrythe typenumber, andnode1 = list1givesnode1the type oflist1. No annotations are needed. - A boolean is not a number. Writing
carry = digitSum > 9makes the compiler report thatbooleanis not assignable tonumber. Types are erased, so the compiled JavaScript would still run, butcarrywould holdtrueinstead of a number. The ternary stores a real 1 or 0. - Truthiness. In
while (node1 || node2 || carry), objects count as true,nulland0count as false. One condition covers all three cases. - Several variables in one
let. Inlet head = new ListNode(), tail = head;, the second variable is initialised from the first. Both refer to the same node at first, and onlytailmoves afterwards.new ListNode()without arguments relies on the class's default value, which is 0. %=.digitSum %= 10is shorthand fordigitSum = digitSum % 10. For the non-negative sums here, it leaves the ones digit.- Why
headis never reassigned. It keeps pointing at the dummy node, which is how the final line finds the start of the real result.
Complexity
Let m and n be the lengths of the two lists.
Time: O(max(m, n)). The loop runs once per column, up to the longer length plus at most one extra column for a final carry. Each iteration does a constant amount of work.
Space: O(max(m, n)). The result list has one node per column, which is required by the output. Beyond that, the method uses a few variables.
Edge cases and common mistakes
- A final carry.
[5]plus[5]gives[0, 1]. Leavingcarryout of the loop condition would return[0]and lose the digit. - Different lengths.
[1]plus[9, 9]gives[0, 0, 1]: the carry travels through the longer list after the shorter one ends. - Zero.
[0]plus[0]gives[0]. The loop runs once and stops, with no extra node. - Using
elsefor the second list. This skips digits oflist2wheneverlist1still has digits, and the result is wrong. - Not moving
tail. Withouttail = tail.next, every digit overwriteshead.next, and the answer ends up as just the last digit. - Returning
head. That includes the dummy node, so the result starts with a stray 0. - Converting to numbers. Parsing the lists to numbers and adding them gives wrong answers for long lists, because of the precision limit described above.
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]and[9, 9]give[0, 0, 1].