445. Add Two Numbers II

/**

 * 445. Add Two Numbers II

 * You are given two non-empty linked lists representing two non-negative integers.

 * The most significant digit comes

 * first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

 *

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

 *

 * Follow up:

 * What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

 *

 * Example:

 *

 * Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

 * Output: 7 -> 8 -> 0 -> 7

*/

See the solution at github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/linked_list/LinkedListTwoNumbers.java

Observation: We need to iterate over the two lists while adding their sum into a new list. However, when we add their sum its possible that the sum at a certain index will be larger or equal to 10. Thus, we need to run another loop to correct the values in the list so they are in a correct range 0-9 (current value + carry % 10) and calculate carry as (current value + carry) / 10. Lastly, we need to create another node to process the last carry if it was not 0.

The code below can be simplified via copying the two lists into two stacks and then work off of values in the two stacks until they are empty while processing carry in same loop as one where the stacks are merged.

Code:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // find the length of both lists
    int n1 = 0, n2 = 0;
    ListNode curr1 = l1, curr2 = l2;
    while (curr1 != null) {
        curr1 = curr1.next;
        ++n1;
    }
    while (curr2 != null) {
        curr2 = curr2.next;
        ++n2;
    }

    // parse both lists
    // and sum the corresponding positions
    // without taking carry into account
    // 3->3->3 + 7->7 --> 3->10->10--> 10->10->3
    curr1 = l1;
    curr2 = l2;
    ListNode head = null;
    while (n1 > 0 && n2 > 0) {
        int val = 0;
        if (n1 >= n2) {
            val += curr1.val;
            curr1 = curr1.next;
            --n1;
        }
        if (n1 < n2) {
            val += curr2.val;
            curr2 = curr2.next;
            --n2;
        }

        // update the result: add to front
        ListNode curr = new ListNode(val);
        curr.next = head;
        head = curr;
    }

    // take the carry into account
    // to have all elements to be less than 10
    // 10->10->3 --> 0->1->4 --> 4->1->0
    curr1 = head;
    head = null;
    int carry = 0;
    while (curr1 != null) {
        // current sum and carry
        int val = (curr1.val + carry) % 10;
        carry = (curr1.val + carry) / 10;

        // update the result: add to front
        ListNode curr = new ListNode(val);
        curr.next = head;
        head = curr;

        // move to the next elements in the list
        curr1 = curr1.next;
    }

    // add the last carry
    if (carry != 0) {
        ListNode curr = new ListNode(carry);
        curr.next = head;
        head = curr;
    }

    return head;
}