Problem overview
The function addTwoNumbers receives list1 and list2, two non-empty linked lists of *ListNode. 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 function returns their sum in the same format, as a new list.
For [2, 4, 3] and [5, 6, 4] the numbers are 342 and 465. Their sum, 807, is returned as [7, 0, 8]. For [9, 9, 9, 9, 9, 9, 9] and [9, 9, 9, 9] the numbers are 9999999 and 9999, the sum is 10009998, and the result is [8, 9, 9, 9, 0, 0, 0, 1]. This one is longer than either input, because the last carry creates a new digit.
Approach: do what you do on paper
Reverse order is convenient here. Column addition on paper starts at the ones digit, and the lists start there too. So the algorithm walks both lists at once from the front. For each column it adds the two digits (a missing digit counts as 0) plus the carry from the previous column. The digit to store is sum % 10 and the new carry is sum / 10.
The largest possible column sum is 9 + 9 + 1 = 19, so the carry is always 0 or 1.
The loop must continue while either list has digits left or a carry is pending. The carry condition matters at the very end: adding [5] and [5] leaves both lists empty after one column, but the sum 10 still has a carry of 1, which needs a second node. The result is [0, 1].
The result list is built by appending at its tail. To avoid a special case for the first node, the code starts with a dummy node and returns dummy.Next at the end.
Step by step
- Create two cursors,
node1, node2 := list1, list2. One:=declares both. The cursors move, while the parameters stay put. - Create the dummy:
dummy := &ListNode{}. The&before a struct literal gives a pointer to a new node, with fields left out set to zero. - Point
tailat the dummy.tailis the last node of the result so far. At first it is the dummy, so the first appended digit becomesdummy.Next. - Start
carryat 0. - Loop with a condition-only
for(Go'swhile):node1 != nil || node2 != nil || carry > 0. Go conditions must be booleans, so each test is spelled out. - Start the column sum with the carry:
sum := carry. Declaring it inside the loop gives each column a fresh variable. - Add list 1's digit if it exists, then advance
node1. An exhausted list contributes nothing, which is the same as a 0 digit. - Do the same for list 2. The two checks are independent, so lists of different lengths work.
- Update the carry:
carry = sum / 10. Integer division in Go drops the remainder, so this is 1 for sums of 10 to 19 and 0 below 10. - Append the digit:
tail.Next = &ListNode{Val: sum % 10}. The remainder after dividing by 10 is the last digit of the sum. - Advance
tailonto the new node. Without this, each digit would overwrite the previous one. - Return
dummy.Next, the first real digit.
The solution in Go
func addTwoNumbers(list1, list2 *ListNode) *ListNode {
node1, node2 := list1, list2
dummy := &ListNode{}
tail := dummy
carry := 0
for node1 != nil || node2 != nil || carry > 0 {
sum := carry
if node1 != nil {
sum += node1.Val
node1 = node1.Next
}
if node2 != nil {
sum += node2.Val
node2 = node2.Next
}
carry = sum / 10
tail.Next = &ListNode{Val: sum % 10}
tail = tail.Next
}
return dummy.Next
}
Go details worth knowing:
- Tuple declarations.
node1, node2 := list1, list2evaluates the right side first and then assigns in order. It's the same as two separate declarations. - Integer division and remainder. With
intoperands,/truncates toward zero and%takes the sign of the dividend. All values here are non-negative, sosum / 10andsum % 10are the carry and the digit. - No truthiness. A pointer or an integer can't stand alone as a condition, so the code writes
node1 != nilandcarry > 0. - Composite literals.
&ListNode{Val: sum % 10}names the field it sets.Nextis left asnil, which is right for a new tail node. - No big integers needed. The code never converts the lists into a number. The lists can be far longer than what an
intholds, because only one column is ever in a variable.
Complexity
Time: O(max(m, n)), where m and n are the lengths. Each iteration consumes one digit from at least one list, except possibly the last, which only writes the final carry. The work per iteration is constant.
Space: O(max(m, n)) for the result list, which has one node per column, plus one for a final carry. Apart from the output, the extra memory is a few variables.
Edge cases and common mistakes
- Lists of different lengths.
[9, 9, 9, 9, 9, 9, 9]plus[9, 9, 9, 9]keeps going after the second list is exhausted. The carry moves through the remaining 9s, turning them into 0s, until it becomes a new 1 at the end. - Final carry.
[5]plus[5]gives[0, 1]. A loop condition of onlynode1 != nil || node2 != nilwould return[0], which means 0. - Zero.
[0]plus[0]gives[0]: one column, sum 0, no carry. - Dereferencing an exhausted list. Reading
node2.Valwithout thenode2 != nilcheck panics once the shorter list ends. - Forgetting to advance
tail. The result would keep only the last digit, replacing the earlier ones. - Returning
dummy. That adds a leading 0 node to every answer.
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].[5]and[5]gives[0, 1].[0]and[0]gives[0].