Grokking 75: Top Coding Interview Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Add Two Numbers
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You are given two non-empty linked lists that represent two non-negative integers, where each node contains the single digit. The digits are stored in reverse order. Add these two numbers and return the sum as a linked list.

You can assume the numbers do not have leading zeros, except for the number 0 itself.

Examples

Example 1:

  • Input: l1: [1, 2, 3], l2: [4, 5, 6]
  • Expected Output: [5, 7, 9]
  • Justification: 321 + 654 = 975, which in reverse order is [5, 7, 9].

Example 2:

  • Input: l1: [7, 8], l2: [6, 7, 8, 9]
  • Expected Output: [3, 6, 9, 9]
  • Justification: 87 + 9876 = 9963, which in reverse order is [3, 6, 9, 9].

Example 3:

  • Input: l1: [0], l2: [0]
  • Expected Output: [0]
  • Justification: 0 + 0 = 0, which in reverse order is [0].

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

Solution

To solve this problem, we will iterate through both linked lists while adding corresponding digits along with any carry from the previous addition. We'll start from the least significant digit (head of the list). If the sum of the digits and carry is 10 or more, we'll set the current node value to the remainder when divided by 10 and carry forward the quotient. This approach ensures that we handle all digit additions and carries correctly as we move through the lists.

This approach works well because it mimics the manual addition process, dealing with each digit and carrying over values as needed. It efficiently handles linked lists of different lengths by continuing to process the longer list once the shorter one is exhausted, ensuring that all digits are accounted for in the final sum.

Step-by-Step Algorithm

  • Initialize a dummy node to act as the starting point of the result linked list.
  • Set a pointer current to this dummy node.
  • Initialize a variable carry to 0.
  • Loop through the lists until both are exhausted:
    • Sum the current digits of both lists and the carry.
    • Update carry to be the floor division of the sum by 10.
    • Set the next node's value to the sum modulo 10.
    • Move the current pointer to the next node.
    • Move to the next node in each input list if available.
  • After the loop, if carry is not zero, add a new node with the carry value.
  • Return the next node of the dummy node as the head of the result linked list.

Algorithm Walkthrough

Let's walk through the algorithm step-by-step with the input l1: [7, 8] and l2: [6, 7, 8, 9].

  1. Initialization:

    • Create a dummy node to act as the head of the result list.
    • Set a current pointer to the dummy node.
    • Initialize a carry variable to 0.

  2. First Iteration:

    • Add the values of the first nodes of l1 and l2, plus the carry:
      • sum = 7 (l1) + 6 (l2) + 0 (carry) = 13
    • Calculate the new carry and the digit to store in the result list:
      • carry = 13 // 10 = 1
      • current.next = new ListNode(13 % 10) = new ListNode(3)
    • Move the current pointer to the next node:
      • current = current.next
    • Move to the next nodes in l1 and l2:
      • l1 = l1.next (8)
      • l2 = l2.next (7)

  3. Second Iteration:

    • Add the values of the current nodes of l1 and l2, plus the carry:
      • sum = 8 (l1) + 7 (l2) + 1 (carry) = 16
    • Calculate the new carry and the digit to store in the result list:
      • carry = 16 // 10 = 1
      • current.next = new ListNode(16 % 10) = new ListNode(6)
    • Move the current pointer to the next node:
      • current = current.next
    • Move to the next nodes in l1 and l2:
      • l1 = l1.next (null)
      • l2 = l2.next (8)

  4. Third Iteration:

    • Add the values of the current node of l2 (since l1 is null), plus the carry:
      • sum = 0 (l1 is null) + 8 (l2) + 1 (carry) = 9
    • Calculate the new carry and the digit to store in the result list:
      • carry = 9 // 10 = 0
      • current.next = new ListNode(9 % 10) = new ListNode(9)
    • Move the current pointer to the next node:
      • current = current.next
    • Move to the next node in l2:
      • l2 = l2.next (9)

  5. Fourth Iteration:

    • Add the values of the current node of l2 (since l1 is null), plus the carry:
      • sum = 0 (l1 is null) + 9 (l2) + 0 (carry) = 9
    • Calculate the new carry and the digit to store in the result list:
      • carry = 9 // 10 = 0
      • current.next = new ListNode(9 % 10) = new ListNode(9)
    • Move the current pointer to the next node:
      • current = current.next
    • Move to the next node in l2:
      • l2 = l2.next (null)

  6. Final Step:

    • Both l1 and l2 are now null, and the carry is 0, so we don't need to add any more nodes.

  7. Return the Result:

    • Return the node next to the dummy node as the head of the result list.

The final result is the linked list [3, 6, 9, 9].

Code

Python3
Python3
. . . .

Complexity Analysis

  • Time Complexity: O(max(m, n)), where m and n are the lengths of the two input linked lists. We iterate through both lists once.
  • Space Complexity: O(max(m, n)). We create a new linked list that holds the sum of the input linked lists, which could be as long as the longer input list plus one extra node for a possible carry.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible