Problem
You are given two non-empty linked lists, l1 and l2. Each linked list represents a non-negative integer.
The digits are stored in reverse order, and every node contains a single digit.
For example, the number 321 is represented as:
1 -> 2 -> 3This is because the first node stores the ones digit, the second node stores the tens digit, and the third node stores the hundreds digit.
The task is to add the two numbers and return their sum as a linked list in the same reverse-order format.
You may assume that the numbers do not contain leading zeros, except for the number 0 itself.
Examples
Example 1
Input:
l1 = [1, 2, 3]
l2 = [4, 5, 6]
Output:
[5, 7, 9]The linked lists represent the following numbers:
l1: 1 -> 2 -> 3 represents 321
l2: 4 -> 5 -> 6 represents 654Their sum is:
321 + 654 = 975Since the result must also be stored in reverse order, the returned linked list is:
5 -> 7 -> 9Example 2
Input:
l1 = [9]
l2 = [9]
Output:
[8, 1]Here:
9 + 9 = 18The result is stored in reverse order as:
8 -> 1Key Idea
This problem is similar to the way we perform addition by hand.
We add the digits at the same position and keep track of any carry produced by the previous addition.
For every pair of nodes:
- Read the digit from
l1. - Read the digit from
l2. - Add both digits and the current carry.
- Store the last digit of the sum in a new node.
- Carry the remaining value into the next iteration.
For example:
9 + 9 = 18The digit placed in the current node is:
18 % 10 = 8The carry passed to the next position is:
18 // 10 = 1Because the digits are already stored in reverse order, we can process both linked lists from beginning to end without reversing them.
Python Solution
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(
self,
l1: Optional[ListNode],
l2: Optional[ListNode]
) -> Optional[ListNode]:
dummy = curr = ListNode()
carry = 0
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
total = v1 + v2 + carry
carry = total // 10
digit = total % 10
curr.next = ListNode(digit)
curr = curr.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.nextStep-by-Step Explanation
1. Create a dummy node
dummy = curr = ListNode()The dummy node acts as a temporary starting point for the result linked list.
Using a dummy node makes the code simpler because we do not need separate logic for creating the first result node.
The curr pointer is used to append new nodes to the result.
At the end, the actual result begins at:
dummy.next2. Initialize the carry
carry = 0The carry variable stores any value that needs to be added to the next pair of digits.
Initially, there is no carry.
3. Continue while there is something left to process
while l1 or l2 or carry:The loop continues while:
l1still has nodes,l2still has nodes, or- there is a remaining carry.
Including carry in the condition is important.
For example, when adding:
9 + 9 = 18both linked lists end after the first iteration, but we still need another node to store the remaining carry of 1.
4. Read the current digits
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0The linked lists may have different lengths.
When one list ends before the other, its missing digits are treated as 0.
For example:
l1 = 2 -> 4
l2 = 5During the second iteration, l2 has no node, so its value is treated as 0.
5. Calculate the total
total = v1 + v2 + carryWe add the two current digits and the carry from the previous iteration.
6. Calculate the new digit and carry
carry = total // 10
digit = total % 10The remainder after division by 10 becomes the digit stored in the current result node.
The integer division result becomes the carry for the next iteration.
For example, if:
total = 17then:
digit = 17 % 10 = 7
carry = 17 // 10 = 17. Add the digit to the result
curr.next = ListNode(digit)
curr = curr.nextA new node is created with the calculated digit.
The curr pointer then moves forward so that the next result node can be attached.
8. Move through the input lists
l1 = l1.next if l1 else None
l2 = l2.next if l2 else NoneEach pointer advances to the next node when possible.
9. Return the result
return dummy.nextThe dummy node itself is not part of the result, so we return the node after it.
Dry Run
Consider:
l1 = [9]
l2 = [9]First iteration
v1 = 9
v2 = 9
carry = 0Calculate the total:
total = 9 + 9 + 0 = 18Calculate the digit and carry:
digit = 18 % 10 = 8
carry = 18 // 10 = 1The result is now:
8Both input lists have ended, but carry is still 1.
Second iteration
v1 = 0
v2 = 0
carry = 1Calculate the total:
total = 0 + 0 + 1 = 1Calculate the digit and carry:
digit = 1
carry = 0The final result becomes:
8 -> 1Therefore, the returned list is:
[8, 1]Complexity Analysis
Let n be the length of l1 and m be the length of l2.
Time Complexity
O(max(n, m))We process each node from both linked lists at most once.
Space Complexity
O(max(n, m))The result linked list contains at most max(n, m) + 1 nodes.
The extra node is required when the final addition produces a carry.
If the space used by the returned linked list is not counted, the auxiliary space complexity is:
O(1)Important Edge Cases
Lists with different lengths
l1 = [2, 4]
l2 = [5]Missing digits are treated as 0.
A carry after the final nodes
l1 = [9]
l2 = [9]The loop must continue long enough to add the final carry.
One number is zero
l1 = [0]
l2 = [5]The result is:
[5]Conclusion
The main challenge in this problem is correctly managing the carry and handling linked lists of different lengths.
The reverse-order representation makes the addition easier because the least significant digits appear first. This allows us to process the linked lists from left to right, just like digit-by-digit addition.
Using a dummy node also simplifies the construction of the result linked list by removing the need for special handling of the first node.
