Problem overview
Two non-negative integers arrive as linked lists, with one digit per node and the least significant digit first. AddTwoNumbers(list1, list2) must return their sum as a new linked list in the same format. Neither number has leading zeros, except the number 0 itself, and neither list is empty.
In the first example, [2, 4, 3] is the number 342 and [5, 6, 4] is 465. Their sum is 807, which is stored backwards as [7, 0, 8]. In the second example, 9999999 + 9999 = 10009998 produces [8, 9, 9, 9, 0, 0, 0, 1]: the result is one node longer than either input, because a carry survives past the last column.
Approach: add column by column, like on paper
The reversed order is a gift. Addition on paper starts at the rightmost digit and moves left, and these lists start at exactly the digit you need first. So the plan is the schoolbook method:
- Add the two digits in the current column, plus any carry from the previous column.
- Write the last digit of that sum into a new result node.
- Carry 1 into the next column if the sum was 10 or more.
Converting each list to an integer and adding the integers is tempting, but it breaks on long lists, because the numbers can have more digits than any integer type holds. Working digit by digit never builds a large number, so the length doesn't matter. The algorithm visits each node once and runs in linear time.
The lists can have different lengths. Once one list runs out, its missing digits count as 0 and the other list keeps contributing. When both lists are exhausted, a leftover carry still needs one more node, which is why 9999999 + 9999 ends with an extra 1.
Step by step
- Create two cursors.
node1andnode2walk the lists, solist1andlist2keep pointing at the heads. C# allows several variables of one type in a single declaration. - Create a dummy head. The result list needs a first node, but you don't know its value until the first column is added. A throwaway node at the front, with
tailstarting on it, lets every real digit be appended the same way, with no special case for the first one. - Start the carry at 0. The first column has nothing to carry in.
- Loop while there is work. The condition has three parts joined by
||: the first list has a digit, the second list has a digit, or a carry is waiting. The last part is what produces the extra node at the end. - Seed the column sum with the carry. A fresh
digitSumper iteration starts as the carry from the previous column. - Add each list's digit if it exists. Use two separate
ifstatements, notif/else, because both lists usually have a digit in the same column. Each one also moves its cursor forward. - Work out the new carry. A column sum above 9 carries 1 into the next column. The biggest possible sum is 9 + 9 + 1 = 19, so the carry is never more than 1.
- Keep only the last digit.
digitSum %= 10turns 15 into 5 and leaves 7 as 7. - Append a node and move on. Hang the new node on
tail.next, then movetailonto it so the next digit goes after it. - Return
head.next. The dummy node isn't part of the answer, so the result starts just after it.
The solution in C#
class Solution {
public ListNode AddTwoNumbers(ListNode list1, ListNode list2) {
ListNode node1 = list1, node2 = list2;
ListNode head = new ListNode(), tail = head;
int carry = 0;
while (node1 != null || node2 != null || carry > 0) {
int digitSum = carry;
if (node1 != null) {
digitSum += node1.val;
node1 = node1.next;
}
if (node2 != null) {
digitSum += node2.val;
node2 = node2.next;
}
carry = (digitSum > 9) ? 1 : 0;
digitSum %= 10;
tail.next = new ListNode(digitSum);
tail = tail.next;
}
return head.next;
}
}
A few C# details are worth a closer look:
- Booleans are not integers. In some languages
carry = digitSum > 9;stores 1 or 0. In C# that line doesn't compile, because aboolcan't be converted to anint. The conditional operatorcondition ? 1 : 0makes the conversion explicit. Integer division gives another route:carry = digitSum / 10is 1 for sums from 10 to 19 and 0 below that. - Explicit null checks. A condition must be a
bool, sowhile (node1)is not allowed. Writenode1 != null. %=is shorthand.digitSum %= 10meansdigitSum = digitSum % 10.- The dummy node comes from
new ListNode(). Itsvalis 0 by default and it is never returned. BecauseListNodeis a class,tail = headcopies a reference, not the node. Both variables point at the same object, andtail.next = …modifies the list thatheadstill points to. - The cursors are local copies. Moving
node1doesn't changelist1, and the input lists are never modified.
Complexity
Time: O(max(m, n)), where m and n are the lengths of the two lists. Each iteration consumes one digit from each list that still has one, and there is at most one extra iteration for the final carry.
Space: O(max(m, n)) for the result list, which is the output itself. Apart from that, the code uses a few variables, so the extra space is O(1).
Edge cases and common mistakes
- A carry after the last digit.
[5]plus[5]must give[0, 1]. A loop that only checks the two lists stops after the first column and loses the 1. - Different lengths.
[1, 8]plus[0]works because the missing digit counts as 0. Readingnode2.valwithout a null check would throw aNullReferenceException. - Zero plus zero.
[0]plus[0]gives[0], one node. The loop runs once, and nothing is carried, so it stops. - A carry chain. Adding
[9, 9, 9]and[1]carries through every column and ends with[0, 0, 0, 1]. - Using
if/elsefor the two lists. That adds only one list's digit per column. - Forgetting to advance
tail. Each new digit would overwrite the previous one and the result would hold at most one real node. - Returning
head. That includes the dummy node, which puts an extra 0 at the front.
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].