2. Add Two Numbers
Problem Description
Imagine you have two numbers, but instead of writing them down in the usual way, you write each digit down separately, in reverse order, and then link all these digits together into a chain where each link is a single digit. These chains are what we call linked lists in computer science, and each digit lives in its own node, a little container with the number and a pointer to the next digit in the list.
Now, let's say someone gives you two of these chains, both representing non-negative integers, and asks you to add these numbers together just like you would on a piece of paper. But here's the twist: the result should be presented in the same reversed chain format.
The problem resembles simple addition, starting from the least significant digit (which is at the head of the chain because of the reverse order) and moving up to the most significant one, carrying over any overflow.
And there's one more thing - if our numbers were zeroes, they wouldn't have any leading digits, except for a single zero node to represent the number itself.
The challenge here is to simulate this familiar arithmetic operation using the rules and structures of linked lists.
Intuition
Adding two numbers is something we learn early in school, and the process is almost second nature - start with the rightmost digits, add them, carry over if needed, and move left. Doing this with linked lists means mimicking this step-by-step addition. However, linked lists don't allow us to access an element directly by position; we traverse from the start node to the end node.
We start the simulation by simultaneously walking down both linked lists - these are our two numbers in reverse order. At each step, we sum the current digit of each number along with any carry left over from the previous step.
We keep track of the carry-over because, during addition, if we add two digits and the sum is 10 or higher, we need to carry over the '1' to the next set of digits. In coding terms, think of 'carry' as a temporary storage space where we keep that extra digit.
To hold our resulting number, we create a new linked list (we'll call it the 'sum list'). For each pair of digits we add, we'll create a new node in the 'sum list' that contains the result of the addition modulo 10 (which is the remainder after division by 10 ā basically, the digit without the carry part). The carry (if any) is computed as the floor division of the sum by 10.
We continue traversing both input lists, adding corresponding digits and carry as we go. If one list is longer, we simply carry on with the digits that remain. After we've exhausted both lists, if there's still a carry, it means we need one more node with the value of the carry.
When we're done adding, we simply return the head of our 'sum list', and voilĆ , that's our total, neatly reversed just as we started.
Learn more about Recursion, Linked List and Math patterns.
Solution Approach
As outlined in the reference solution approach, we simulate the addition process using a simple iterative method. In computational terms, this is relatively straightforward.
Firstly, we need a placeholder for the sum of the two numbers, which in this case will be a new linked list. We create a dummy
node that acts as the head of our sum list. This dummy
node is very handy because it allows us to easily return the summed list at the end, avoiding the complexities of handling where the list begins in the case of an overflow on the most significant digit.
We initialize two variables:
- The
carry
variable (starting at0
), to keep track our carryover in each iteration. - The
curr
variable, which points to the current node in the sum list; initially, this is set to thedummy
node.
We enter a loop that traverses both input linked lists. The loop continues as long as at least one of the following conditions holds true: there is at least one more node in either l1
or l2
, or there is a non-zero value in carry
. Within the loop:
- We sum the current digit from each list (
l1.val
andl2.val
) with the current carry. If we've reached the end of a list, we treat the missing digits as0
. - The sum produced can be broken down into two parts: the digit at the current position, and the carryover for the next position. This is computed using
divmod(s, 10)
which gives us the quotient representingcarry
and the remainder representingval
ā the current digit to add to our sum list. - We create a new node for
val
and find its place at the end of the sum list indicated bycurr.next
. - We update
curr
to point to this newly added node. - We update
l1
andl2
to point to their respective next nodes ā moving to the next digit or setting toNone
if we've reached the end of the list.
The loop exits once there are no more digits to add and no carry. Since dummy
was only a placeholder, the actual resultant list starts from dummy.next
.
Lastly, we return dummy.next
, which points to the head of the linked list representing the sum of our two numbers. The way our loop is structured ensures that this process carries out the addition operation correctly for linked lists of unequal lengths as well, without any additional tweaks or condition checks.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, consider two linked lists representing the numbers 342 and 465. The linked lists would look like this:
l1
: 2 -> 4 -> 3 (Representing 342 written in reverse as a linked list)l2
: 5 -> 6 -> 4 (Representing 465 written in reverse as a linked list)
According to the solution:
-
Initialize a
dummy
node to serve as the head of the new linked list that will store our result. -
Set a
carry
variable to0
andcurr
to point todummy
. -
Iterate over
l1
andl2
as long as there is a node in either list orcarry
is not zero.For the first iteration:
l1.val
is2
, andl2.val
is5
. The sum is2 + 5 + carry (0) = 7
.- The digit for the new node is
7 % 10 = 7
, and the new carry is7 // 10 = 0
. - Create a new node with a value of
7
and link it tocurr
.
The resulting list is now 7
, the dummy
node points to 7
, and curr
also points to 7
.
Continuing to the second digit:
l1.val
is4
,l2.val
is6
. The sum is4 + 6 + carry (0) = 10
.- The digit for the new node is
10 % 10 = 0
, and the new carry is10 // 10 = 1
. - Create a new node with a value of
0
and link it tocurr
.
Now, the resulting list is 7 -> 0
, dummy
points to 7
, and curr
points to 0
.
For the third digit:
l1.val
is3
,l2.val
is4
. The sum is3 + 4 + carry (1) = 8
.- The digit for the new node is
8 % 10 = 8
, and the new carry is8 // 10 = 0
. - Create a new node with a value of
8
and link it tocurr
.
Our final list becomes 7 -> 0 -> 8
, which is the reverse of 807
, the sum of 342
and 465
.
After the end of the loop, we check to see if carry
is non-zero. In this case, it's zero, so we do not add another node.
Lastly, since the dummy
was just a placeholder, we return dummy.next
, which gives us 7 -> 0 -> 8
, the final linked list representing our summed number in reverse order.
Solution Implementation
1class ListNode:
2 def __init__(self, value=0, next_node=None):
3 self.value = value
4 self.next_node = next_node
5
6class Solution:
7 def addTwoNumbers(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
8 # Initialize a dummy head to build the result list
9 dummy_head = ListNode()
10 # Initialize the current node to the dummy head and a carry variable
11 carry, current = 0, dummy_head
12
13 # Loop until both lists are exhausted and there is no carry left
14 while list1 or list2 or carry:
15 # Calculate the sum using the values of the current nodes and the carry
16 sum_ = (list1.value if list1 else 0) + (list2.value if list2 else 0) + carry
17 # Update carry for next iteration (carry, if any, would be 1)
18 carry, value = divmod(sum_, 10)
19 # Create the next node with the sum value mod 10
20 current.next_node = ListNode(value)
21 # Move to the next node on the result list
22 current = current.next_node
23 # Move to the next nodes on the input lists, if available
24 list1 = list1.next_node if list1 else None
25 list2 = list2.next_node if list2 else None
26
27 # Return the result list, which starts from the dummy head's next node
28 return dummy_head.next_node
29
1// Definition for singly-linked list.
2class ListNode {
3 int val;
4 ListNode next;
5 ListNode() {}
6 ListNode(int val) { this.val = val; }
7 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
8}
9
10class Solution {
11 public ListNode addTwoNumbers(ListNode firstList, ListNode secondList) {
12 // Create a dummy node which will be the starting point of the result list.
13 ListNode dummyNode = new ListNode(0);
14
15 // This variable will keep track of the carry-over.
16 int carry = 0;
17
18 // This will be used to iterate over the new list.
19 ListNode current = dummyNode;
20
21 // Iterate as long as there is a node left in either list or there is a carry-over.
22 while (firstList != null || secondList != null || carry != 0) {
23 // Sum the values of the two nodes if they are not null, else add 0.
24 int sum = (firstList == null ? 0 : firstList.val) +
25 (secondList == null ? 0 : secondList.val) + carry;
26
27 // Update carry for the next iteration.
28 carry = sum / 10;
29
30 // Create a new node with the digit value of the sum.
31 current.next = new ListNode(sum % 10);
32
33 // Move to the next node in the result list.
34 current = current.next;
35
36 // Proceed in each input list.
37 firstList = firstList == null ? null : firstList.next;
38 secondList = secondList == null ? null : secondList.next;
39 }
40
41 // The first node was a dummy node, so the real list starts at dummyNode.next.
42 return dummyNode.next;
43 }
44}
45
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode() : val(0), next(nullptr) {}
7 * ListNode(int x) : val(x), next(nullptr) {}
8 * ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13 // Function to add two numbers represented by two linked lists
14 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
15 // Initialize a dummy head to build the result list
16 ListNode* dummyHead = new ListNode();
17 // Variable to keep track of the carry
18 int carry = 0;
19 // We use 'current' to add new nodes to the result list
20 ListNode* current = dummyHead;
21 // Continue looping until both lists are traversed completely and there is no carry
22 while (l1 || l2 || carry) {
23 // Calculate the sum of the current digits along with the carry
24 int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
25 // Update the carry for the next iteration
26 carry = sum / 10;
27 // Create a new node with the digit part of the sum and append to the result list
28 current->next = new ListNode(sum % 10);
29 // Move the 'current' pointer to the new node
30 current = current->next;
31 // Move the list pointers l1 and l2 to the next nodes if they exist
32 l1 = l1 ? l1->next : nullptr;
33 l2 = l2 ? l2->next : nullptr;
34 }
35 // The result list starts after the dummy head's next pointer
36 return dummyHead->next;
37 }
38};
39
1// ListNode class definition for a singly-linked list.
2class ListNode {
3 val: number;
4 next: ListNode | null;
5 constructor(val?: number, next?: ListNode | null) {
6 this.val = val === undefined ? 0 : val;
7 this.next = next === undefined ? null : next;
8 }
9}
10
11// Adds two numbers represented by two singly linked lists (l1 and l2) and returns the sum as a linked list.
12function addTwoNumbers(list1: ListNode | null, list2: ListNode | null): ListNode | null {
13 // A dummy head node for the resulting linked list, used to simplify appending new nodes.
14 const dummyHead = new ListNode();
15 // The current node in the resulting linked list as we are building it.
16 let currentNode = dummyHead;
17 // The sum variable carries value when we need to 'carry' a digit to the next decimal place.
18 let carry = 0;
19
20 // Iterate while there is something to add, or we have a carry from the last digits.
21 while (carry !== 0 || list1 !== null || list2 !== null) {
22 // Add the values from list1 and list2 to the carry if they are available.
23 if (list1 !== null) {
24 carry += list1.val;
25 list1 = list1.next; // Move to the next node in list1.
26 }
27 if (list2 !== null) {
28 carry += list2.val;
29 list2 = list2.next; // Move to the next node in list2.
30 }
31 // The new digit is the remainder of sum when divided by 10.
32 currentNode.next = new ListNode(carry % 10);
33 // Move to the newly created node.
34 currentNode = currentNode.next;
35 // Calculate the new carry, which is the floor division of sum by 10.
36 carry = Math.floor(carry / 10);
37 }
38 // Return the next node of dummyHead to skip the dummy node at the beginning.
39 return dummyHead.next;
40}
41
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(max(m, n))
, where m
and n
are the lengths of the input linked lists l1
and l2
, respectively. This is because we iterate through both lists in parallel, and at each step, we add the corresponding nodes' values along with any carry from the previous step, which takes constant time O(1)
. The iteration continues until both lists have been fully traversed and there is no carry left to add.
Space Complexity
The space complexity of the code is O(1)
, ignoring the space consumption of the output list. The variables carry
, curr
, and the nodes we iterate through (l1
and l2
) only use a constant amount of space. However, if we take into account the space required for the result list, the space complexity would be O(max(m, n))
, since in the worst case, the resultant list could be as long as the longer of the two input lists, plus one extra node for an additional carry.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Want a Structured Path to Master System Design Too? Donāt Miss This!