0445. Add Two Numbers II

https://leetcode.com/problems/add-two-numbers-ii

Description

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

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

Example 1:

**Input:** l1 = [7,2,4,3], l2 = [5,6,4]
**Output:** [7,8,0,7]

Example 2:

**Input:** l1 = [2,4,3], l2 = [5,6,4]
**Output:** [8,0,7]

Example 3:

**Input:** l1 = [0], l2 = [0]
**Output:** [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.

Follow up: Could you solve it without reversing the input lists?

ac

O(1) space but actually you don't need to do that, because recursion's space complexity is O(n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // get length
        int len1 = getListLength(l1);
        int len2 = getListLength(l2);

        // get longer one
        ListNode lng = l1, shrt = l2;
        if (len1 < len2) {
            lng = l2; shrt = l1;
        }

        // walk to same length;
        ListNode dummy = new ListNode(0);
        dummy.next = lng;
        ListNode lng2 = dummy;
        int diff = Math.abs(len1 - len2);
        for (int i = 0; i < diff; i++) {
            lng2 = lng2.next;
        }

        int carry = add(lng2.next, shrt);

        addCarry(dummy, carry, diff);

        return dummy.val > 0 ? dummy : dummy.next;
    }

    private int addCarry(ListNode node, int carry, int dist) {
        // exit
        if (dist == 0) {
            int curr = node.val + carry;
            node.val = curr % 10;
            return curr / 10;
        }

        int nextCarry = addCarry(node.next, carry, dist-1);
        int curr2 = node.val + nextCarry;
        node.val = curr2 % 10;
        return curr2 / 10;
    }

    private int add(ListNode lng, ListNode shrt) {
        // exit
        if (lng == null && shrt == null) return 0;

        int carry = add(lng.next, shrt.next);
        int curr = lng.val + shrt.val + carry;
        lng.val = curr % 10;
        return curr / 10;
    }

    private int getListLength(ListNode node) {
        int len = 0;
        ListNode nodeRanger = node;
        while (nodeRanger != null) {
            len++;
            nodeRanger = nodeRanger.next;
        }
        return len;
    }
}
/*
get length
walk to same length
recursion update long list
take care of last carry
*/

ac2: 2 stack

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<>();        
        Stack<Integer> s2 = new Stack<>();        

        while (l1 != null) {
            s1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            s2.push(l2.val);
            l2 = l2.next;
        }

        int carry = 0;
        ListNode head = null;
        while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
            int curr = carry;
            curr += !s1.isEmpty() ? s1.pop() : 0;
            curr += !s2.isEmpty() ? s2.pop() : 0;
            carry = curr / 10;
            ListNode newNode = new ListNode(curr % 10);
            newNode.next = head;
            head = newNode;
        }

        return head;
    }
}
/*
two stack

*/