Introduction to Add Two Numbers in Go
The "Add Two Numbers" problem is one of the most iconic algorithmic challenges on platforms like LeetCode. It tests your understanding of linked lists, digit-by-digit arithmetic, and carry propagation. While the problem sounds deceptively simple — just add two numbers — the twist is that the numbers are stored in reverse order as singly linked lists, where each node contains a single digit.
In this tutorial, we'll walk through solving this problem using Go (Golang). Go's simplicity, strong typing, and built-in support for structs and pointers make it an excellent language for tackling linked list problems. By the end, you'll understand not only how to solve this specific problem but also how to reason about similar linked list and arithmetic challenges.
What Is the Add Two Numbers Problem?
Given two non-empty linked lists representing two non-negative integers, where digits are stored in reverse order (least significant digit first), add the two numbers and return the sum as a linked list in the same reverse order format.
For example, the number 342 is represented as 2 -> 4 -> 3, and 465 is represented as 5 -> 6 -> 4. Adding them produces 807, which is returned as 7 -> 0 -> 8.
Problem Constraints
- Each list node contains a single digit between 0 and 9.
- The lists are non-empty and do not contain leading zeros (except for the number zero itself).
- The numbers can be arbitrarily large, meaning they won't fit into standard integer types — hence the linked list representation.
Why This Problem Matters
Understanding this problem is foundational for several reasons. First, it teaches you how to traverse and manipulate linked lists, a data structure that appears in many real-world systems such as memory allocators, hash table buckets, and LRU caches. Second, it forces you to handle carry propagation, a concept that generalizes to big integer arithmetic, binary addition, and even hardware-level adder circuits.
From an interview perspective, this problem evaluates your ability to:
- Correctly initialize and build a new linked list from scratch.
- Manage multiple pointers and edge cases simultaneously.
- Reason about loop termination conditions and final carry handling.
- Write clean, idiomatic code under pressure.
Defining the Linked List Structure in Go
Before solving the problem, we need to define the linked list node. In Go, we use a struct with a value field and a pointer to the next node.
package main
// ListNode represents a singly linked list node.
type ListNode struct {
Val int
Next *ListNode
}
This struct is the building block for our solution. The Val field holds the digit, and Next points to the subsequent node (or nil if it's the last node).
Step-by-Step Solution
Step 1: Understand the Algorithm
The core idea is to traverse both lists simultaneously, adding corresponding digits along with any carry from the previous step. Since the lists are stored in reverse order, we start from the least significant digit, which means we can process them head-to-tail without reversing.
At each step:
- Sum the current digits from both lists (if available) plus the carry.
- The new digit is
sum % 10. - The new carry is
sum / 10. - Append a new node with the computed digit to the result list.
- Advance the pointers of both input lists.
After the loop, if a carry remains, append one final node with that carry value.
Step 2: Implement the Solution
Here is the complete implementation of the addTwoNumbers function:
package main
// ListNode represents a singly linked list node.
type ListNode struct {
Val int
Next *ListNode
}
// addTwoNumbers adds two numbers represented as reversed linked lists.
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
current := 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
}
carry = sum / 10
current.Next = &ListNode{Val: sum % 10}
current = current.Next
}
return dummy.Next
}
Step 3: Understand the Dummy Head Pattern
Notice the use of a dummy head node. This is a common technique in linked list problems. Instead of special-casing the first node (which would require checking whether the result list is empty on every iteration), we create a placeholder node and always append to current.Next. At the end, we return dummy.Next, which is the real head of our result list.
This pattern eliminates conditional branches inside the loop and makes the code cleaner and less error-prone.
Step 4: Handle the Carry in the Loop Condition
A subtle but important detail is the loop condition: l1 != nil || l2 != nil || carry != 0. The third condition ensures that if both lists are exhausted but a carry remains (for example, 5 + 5 = 10), we still create one more node to hold the leading 1. Without this condition, the result would be incorrect for inputs that produce a final carry.
Testing the Solution
To verify our solution works correctly, let's write a helper function to build a linked list from a slice of integers, and another to convert a linked list back to a slice for easy comparison.
package main
import "fmt"
// buildList creates a linked list from a slice of digits.
func buildList(digits []int) *ListNode {
dummy := &ListNode{}
current := dummy
for _, d := range digits {
current.Next = &ListNode{Val: d}
current = current.Next
}
return dummy.Next
}
// listToSlice converts a linked list back to a slice of digits.
func listToSlice(head *ListNode) []int {
result := []int{}
for head != nil {
result = append(result, head.Val)
head = head.Next
}
return result
}
func main() {
// Test case 1: 342 + 465 = 807
l1 := buildList([]int{2, 4, 3})
l2 := buildList([]int{5, 6, 4})
result := addTwoNumbers(l1, l2)
fmt.Println(listToSlice(result)) // Output: [7 0 8]
// Test case 2: 0 + 0 = 0
l3 := buildList([]int{0})
l4 := buildList([]int{0})
result2 := addTwoNumbers(l3, l4)
fmt.Println(listToSlice(result2)) // Output: [0]
// Test case 3: 9999999 + 9999 = 10009998
l5 := buildList([]int{9, 9, 9, 9, 9, 9, 9})
l6 := buildList([]int{9, 9, 9, 9})
result3 := addTwoNumbers(l5, l6)
fmt.Println(listToSlice(result3)) // Output: [8 9 9 9 0 0 0 1]
}
Running this program produces the expected outputs, confirming that our implementation handles standard cases, the zero case, and the carry-overflow case correctly.
Complexity Analysis
Understanding the time and space complexity of your solution is essential, especially in interviews and production systems.
- Time Complexity: O(max(m, n)), where m and n are the lengths of the two linked lists. We traverse each list at most once, and the loop runs for the length of the longer list plus potentially one extra iteration for the final carry.
- Space Complexity: O(max(m, n)) for the result list. The output list has at most max(m, n) + 1 nodes, with the extra node accounting for a possible final carry.
This is optimal — you cannot do better than linear time since you must examine every digit, and the output itself requires linear space.
Best Practices
Use the Dummy Head Pattern
Always prefer the dummy head technique when building a new linked list. It simplifies the code by removing the need to handle the first node specially and reduces the chance of nil pointer bugs.
Keep the Loop Condition Comprehensive
Include the carry in your loop condition. A common mistake is to loop only while l1 != nil || l2 != nil and then handle the carry separately. While that works, folding the carry into the loop condition produces more uniform, easier-to-read code.
Avoid Modifying Input Lists
Our solution creates entirely new nodes for the result and never modifies the input lists. This is good practice because callers may still need their original lists. If memory is extremely constrained, you could reuse nodes from one of the input lists, but this should be documented clearly.
Write Helper Functions for Testing
Functions like buildList and listToSlice make testing dramatically easier. They allow you to express test cases as simple slices rather than manually constructing linked lists, which is verbose and error-prone.
Consider Edge Cases Early
Always test these edge cases: both lists being a single zero, lists of unequal length, inputs that produce a final carry, and very long lists. Thinking about these upfront prevents bugs that are hard to trace later.
Common Pitfalls
- Forgetting the final carry: If you only loop while both lists have nodes, you'll miss the case where a carry propagates past the most significant digit.
- Incorrect pointer advancement: Make sure you advance
l1andl2only when they are non-nil. Dereferencing a nil pointer will cause a runtime panic in Go. - Returning the dummy node: Always return
dummy.Next, notdummyitself. The dummy node's value is uninitialized (zero) and is not part of the actual result. - Mixing up digit order: Remember that the lists are in reverse order. This actually simplifies the problem because you process least significant digits first, but if you accidentally reverse the lists first, you add unnecessary complexity.
Conclusion
Solving the Add Two Numbers problem in Go is a great way to build confidence with linked lists, pointer manipulation, and carry-based arithmetic. By using the dummy head pattern, a comprehensive loop condition, and clean helper functions for testing, you can write a solution that is both correct and easy to maintain. The principles you've learned here — careful pointer management, edge case handling, and complexity analysis — transfer directly to more advanced problems involving linked lists, big integer arithmetic, and string manipulation. Practice this solution until you can write it from memory, and you'll be well prepared for interviews and real-world systems programming challenges alike.