You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0] Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]
Constraints:
[1, 100].0 <= Node.val <= 9The key idea in Add Two Numbers is to simulate the process of elementary addition while traversing two linked lists. Each node represents a single digit, and the digits are stored in reverse order. This means the head of each list corresponds to the least significant digit.
You can iterate through both lists simultaneously, adding corresponding digits along with any carry from the previous step. For every sum, create a new node with sum % 10 and update the carry using sum / 10. Continue until both lists are fully processed and no carry remains.
An alternative approach uses recursion to process nodes and propagate the carry automatically through recursive calls. Regardless of the method, the algorithm effectively mirrors manual addition digit by digit. Since each node is visited once, the time complexity depends on the total number of nodes in both lists, while extra space is mainly used for the resulting linked list.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative Linked List Traversal | O(max(m, n)) | O(max(m, n)) |
| Recursive Addition | O(max(m, n)) | O(max(m, n)) (due to recursion stack) |
NeetCode
This approach involves iterating through both linked lists, node by node, adding corresponding values along with any carry from the previous addition. The result at each step is appended to a new linked list. If one list is longer than the other, the iteration continues on the longer list alone. A final check is done to handle any remaining carry.
Time Complexity: O(max(m, n)) where m and n are the lengths of the input lists. This is because we iterate through each node exactly once.
Space Complexity: O(max(m, n)) to store the resulting list.
1#include <stdlib.h>
2
3struct ListNode {
4 int val;
5 struct ListNode *next;
6};
This C implementation employs a dummy head node to start building the resultant list. A 'carry' variable is used to keep track of any overflow beyond a single digit, which is added to the next higher digit. The values are summed, and their result is split into carry and remainder, which becomes the node value. The iteration continues until both input lists are exhausted. The remaining carry is checked to append another node if needed.
The recursive approach solves the problem by recursing down the linked lists, accumulating values with carry and constructing the result linked list from the returned values from child calls. Each recursive call processes one pair of nodes from the lists, similar to how you would process each position in a sum independently in the iterative version.
Time Complexity: O(max(m, n))
Space Complexity: O(max(m, n)) because of the recursion stack.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Add Two Numbers is a classic linked list problem frequently discussed in technical interviews at major tech companies. It tests understanding of linked list traversal, carry handling, and clean pointer manipulation.
The optimal approach is to traverse both linked lists simultaneously while keeping track of a carry value. At each step, add the corresponding digits and create a new node for the result. This mirrors manual addition and runs in linear time.
A singly linked list is the primary data structure used in this problem. It allows digit-by-digit traversal and easy construction of the resulting number while maintaining the required reverse order format.
Storing digits in reverse order simplifies addition because the least significant digit comes first. This allows you to process the lists from head to tail while naturally handling carry values, similar to how manual addition works.
In this C solution, we define a helper function addTwoNumbersRecursive that takes the two input lists and a carry. The function recursively creates new nodes based on the summed values ensuring that carry is also considered. The base case returns NULL when ends of both lists and no carry remain.