2. Add Two Numbers

MediumRecursionLinked ListMath
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used to implement recursion?

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 at 0), 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 the dummy 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 and l2.val) with the current carry. If we've reached the end of a list, we treat the missing digits as 0.
  • 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 representing carry and the remainder representing val – 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 by curr.next.
  • We update curr to point to this newly added node.
  • We update l1 and l2 to point to their respective next nodes – moving to the next digit or setting to None 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example 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:

  1. Initialize a dummy node to serve as the head of the new linked list that will store our result.

  2. Set a carry variable to 0 and curr to point to dummy.

  3. Iterate over l1 and l2 as long as there is a node in either list or carry is not zero.

    For the first iteration:

    • l1.val is 2, and l2.val is 5. The sum is 2 + 5 + carry (0) = 7.
    • The digit for the new node is 7 % 10 = 7, and the new carry is 7 // 10 = 0.
    • Create a new node with a value of 7 and link it to curr.

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 is 4, l2.val is 6. The sum is 4 + 6 + carry (0) = 10.
  • The digit for the new node is 10 % 10 = 0, and the new carry is 10 // 10 = 1.
  • Create a new node with a value of 0 and link it to curr.

Now, the resulting list is 7 -> 0, dummy points to 7, and curr points to 0.

For the third digit:

  • l1.val is 3, l2.val is 4. The sum is 3 + 4 + carry (1) = 8.
  • The digit for the new node is 8 % 10 = 8, and the new carry is 8 // 10 = 0.
  • Create a new node with a value of 8 and link it to curr.

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
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer technique does Quick Sort use?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

Recursion Review

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

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 Basics

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫