Problem

You are working at an accounting firm and need to combine financial reports from two different departments, let’s say Marketing and Sales. These reports are provided to you in electronic format as linked lists of numbers. Each node in the linked list represents one digit of a larger number. The digits are arranged in reverse order because this is how they were stored in their original databases.

Your task is to create a combined financial report by adding the numbers from both departmental reports. This requires you to traverse both linked lists, starting from the head (leftmost) node and moving towards the tail (rightmost). As you add the digits of each position, you also need to carry over any value resulting from the addition that is greater than 9 (i.e., tens place). This new carried-over value will become the next digit in the combined number.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [3,4,2], l2 = [4,6,5] Output: [7,0,8] Explanation: 243 + 564 = 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:

  • 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.

Java Solution

class Solution {
  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    int carry = 0;

    while (l1 != null || l2 != null || carry > 0) {
      if (l1 != null) {
        carry += l1.val;
        l1 = l1.next;
      }
      if (l2 != null) {
        carry += l2.val;
        l2 = l2.next;
      }
      current.next = new ListNode(carry % 10);
      carry /= 10;
      current = current.next;
    }

    return dummy.next;
  }
}
  1. Initialize a dummy ListNode with a value of 0.
  2. Set current to that dummy ListNode, and set carry to 0.
  3. Iterate over the list nodes of l1 and l2, as well as the carry, in a while loop until all are null or 0.
  4. Calculate the sum of the node values and carry, store the carry for the next iteration, and store the value % 10 in a new ListNode connected to the current ListNode.
  5. Shift the current ListNode, l1, and l2 to the next node if available.
  6. Return the next of the dummy ListNode as a result.

C++ Solution

class Solution {
 public:
  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* current = &dummy;
    int carry = 0;

    while (l1 != nullptr || l2 != nullptr || carry > 0) {
      if (l1 != nullptr) {
        carry += l1->val;
        l1 = l1->next;
      }
      if (l2 != nullptr) {
        carry += l2->val;
        l2 = l2->next;
      }
      current->next = new ListNode(carry % 10);
      carry /= 10;
      current = current->next;
    }

    return dummy.next;
  }
};
  1. Initialize a dummy ListNode with a value of 0.
  2. Set current to that dummy ListNode, and set carry to 0.
  3. Iterate over the list nodes of l1 and l2, as well as the carry, in a while loop until all are null or 0.
  4. Calculate the sum of the node values and carry, store the carry for the next iteration, and store the value % 10 in a new ListNode connected to the current ListNode.
  5. Shift the current ListNode, l1, and l2 to the next node if available.
  6. Return the next of the dummy ListNode as a result.

Python Solution

class Solution:
  def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    current = dummy
    carry = 0

    while carry or l1 or l2:
      if l1:
        carry += l1.val
        l1 = l1.next
      if l2:
        carry += l2.val
        l2 = l2.next
      current.next = ListNode(carry % 10)
      carry //= 10
      current = current.next

    return dummy.next
  1. Initialize a dummy ListNode with a value of 0.
  2. Set current to that dummy ListNode, and set carry to 0.
  3. Iterate over the list nodes of l1 and l2, as well as the carry, in a while loop until all are null or 0.
  4. Calculate the sum of the node values and carry, store the carry for the next iteration, and store the value % 10 in a new ListNode connected to the current ListNode.
  5. Shift the current ListNode, l1, and l2 to the next node if available.
  6. Return the next of the dummy ListNode as a result.

JavaScript Solution

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val);
    this.next = (next===undefined ? null : next);
};

function addTwoNumbers(l1, l2) {
    const dummy = new ListNode(0);
    let current = dummy;
    let carry = 0;

    while (l1 || l2 || carry) {
        let sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + carry;
        carry = Math.floor(sum / 10);
        current.next = new ListNode(sum % 10);
        current = current.next;

        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
    }

    return dummy.next;
};
  1. Initialize a dummy ListNode with a value of 0.
  2. Set current to that dummy ListNode, and set carry to 0.
  3. Iterate over the list nodes of l1 and l2, as well as the carry, in a while loop until all are null or 0.
  4. Calculate the sum of the node values and carry, store the carry for the next iteration, and store the value % 10 in a new ListNode connected to the current ListNode.
  5. Shift the current ListNode, l1, and l2 to the next node if available.
  6. Return the next of the dummy ListNode as a result.

After adding all the digits, your final linked list will represent the sum of the two original numbers. The digits in this newly formed linked list should be arranged in reverse order, just like the input lists.

This real-world example mirrors the algorithmic challenge described in the original problem statement, where you need to add two non-negative integers represented as reversed linked lists and return their sum in a reversed format. —>

In this problem, we are given two non-empty linked lists representing two non-negative integers. Each node in these linked lists stores a single digit, and the digits are stored in reverse order. The task is to add these two numbers together and return the result as another linked list with the digits also stored in reverse order.

To solve this problem, we can perform addition on corresponding nodes of both input linked lists while traversing them simultaneously from the head to the tail. We maintain a carry variable to handle cases where the sum exceeds 9. The resulting sum for each pair of nodes is stored as the value in the new node of the output linked list.

Here’s how it works:

  1. Initialize a dummy node as the head of the result linked list, and set up two pointers - curr (initially pointing to the dummy node) and l1Current, l2Current (initially pointing to the heads of the input lists).

  2. Traverse both input linked lists simultaneously until we reach the end of either list or the end of the result list.

  3. For each step, initialize a variable sum to store the sum of the values in the current nodes of both input lists and the carry from the previous addition (if any). Add this value to curr.next.val.

  4. Update the pointers accordingly:

    • Move l1Current and l2Current one step forward if they are not at the end.
    • Set the carry as 1 if the sum is greater than 9, otherwise set it to 0.

  5. Move curr one step forward after each addition step.

  6. After traversing both input lists, check if there’s a remaining carry. If yes, append a new node with the value of the carry at the end of the result list.

  7. Return the head of the resulting linked list (i.e., dummyNode.next).

By performing this algorithm, we can efficiently add two numbers represented by linked lists and obtain the sum as another linked list in reverse order.