medium Add Two Numbers

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

// Definition for singly-linked list
// class ListNode {
//     int val;
//     ListNode next;
//     ListNode(int x) { val = x; }
// }

class Solution {

  // Method to add two numbers represented by linked lists
  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0); // Dummy node to start the result list
    ListNode current = dummy; // Pointer to the current node in the result list
    int carry = 0; // Initialize carry to 0

    // Loop through lists l1 and l2 until both are null
    while (l1 != null || l2 != null) {
      int sum = carry; // Start with the carry from the previous iteration
      if (l1 != null) {
        sum += l1.val; // Add l1's value to sum
        l1 = l1.next; // Move to the next node in l1
      }
      if (l2 != null) {
        sum += l2.val; // Add l2's value to sum
        l2 = l2.next; // Move to the next node in l2
      }
      carry = sum / 10; // Calculate new carry
      current.next = new ListNode(sum % 10); // Create new node with the sum modulo 10
      current = current.next; // Move to the next node in the result list
    }

    // If carry is still greater than 0, add a new node with carry value
    if (carry > 0) {
      current.next = new ListNode(carry);
    }

    return dummy.next; // Return the result list
  }

  // Helper method to print linked list
  private static void printList(ListNode node) {
    while (node != null) {
      System.out.print(node.val + " ");
      node = node.next;
    }
    System.out.println();
  }

  // Main method to test the solution with provided examples
  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    ListNode l1 = new ListNode(1);
    l1.next = new ListNode(2);
    l1.next.next = new ListNode(3);

    ListNode l2 = new ListNode(4);
    l2.next = new ListNode(5);
    l2.next.next = new ListNode(6);

    ListNode result = solution.addTwoNumbers(l1, l2);
    printList(result); // Expected output: 5 7 9

    // Example 2
    l1 = new ListNode(7);
    l1.next = new ListNode(8);

    l2 = new ListNode(6);
    l2.next = new ListNode(7);
    l2.next.next = new ListNode(8);
    l2.next.next.next = new ListNode(9);

    result = solution.addTwoNumbers(l1, l2);
    printList(result); // Expected output: 3 6 9 9

    // Example 3
    l1 = new ListNode(0);
    l2 = new ListNode(0);

    result = solution.addTwoNumbers(l1, l2);
    printList(result); // Expected output: 0
  }
}

Complexity Analysis

• Time Complexity: , where m and n are the lengths of the two input linked lists. We iterate through both lists once.
• Space Complexity: . 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.