Add Two Numbers
MediumThe problem
Two linked lists each represent a non-negative whole number with one digit per node, written in REVERSE order (the first node is the ones digit). Add the two numbers and return the sum as a linked list in the same reversed form.
- Example 1Input: l1 = [2, 4, 3], l2 = [5, 6, 4]Output: [7, 0, 8]
342 + 465 = 807, written backwards as 7, 0, 8.
- Example 2Input: l1 = [9, 9], l2 = [1]Output: [0, 0, 1]
99 + 1 = 100, written backwards as 0, 0, 1.
- Example 3Input: l1 = [0], l2 = [0]Output: [0]
0 + 0 = 0.
- 1 ≤ number of nodes in each list ≤ 10,000
- Each node holds a digit 0 to 9
- No number has leading zeros, except the number 0 itself
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Digits are stored in reverse order — exactly the order you add by hand. What must you carry?
The idea
Walk both lists, sum = a + b + carry, append sum%10, carry = sum/10. Continue while either list or the carry remains.
Target: O(max(n,m)) time
Go function shape
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNodeReference solution
Tested with go test. Try it yourself first, then compare.
// AddTwoNumbers adds two numbers stored as reversed digit lists, exactly like adding on paper:
// add the digits plus the carry, keep the last digit, carry the rest.
func AddTwoNumbers(l1, l2 *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
carry := 0
for l1 != nil || l2 != nil || carry > 0 {
sum := carry
if l1 != nil {
sum += l1.Val
l1 = l1.Next
}
if l2 != nil {
sum += l2.Val
l2 = l2.Next
}
tail.Next = &ListNode{Val: sum % 10}
tail = tail.Next
carry = sum / 10
}
return dummy.Next
}