445. Add Two Numbers II

// LeetCode URL: https://leetcode.com/problems/add-two-numbers-ii/
import java.util.Stack;

//   Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

/**
 * Iterative (No Extra Space)
 *
 * Time Complexity: O(M + N)
 *
 * Space Complexity: O(1)
 *
 * M = Number of nodes in l1. N = Number of nodes in l2.
 */
class Solution1 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode p = l1;
        ListNode q = l2;
        int len1 = 0;
        int len2 = 0;

        while (p != null) {
            len1++;
            p = p.next;
        }
        while (q != null) {
            len2++;
            q = q.next;
        }

        p = l1;
        q = l2;
        ListNode tempHead = null;
        while (len1 > 0 && len2 > 0) {
            int sum = 0;
            if (len1 > len2) {
                sum = p.val;
                p = p.next;
                len1--;
            } else if (len1 < len2) {
                sum = q.val;
                q = q.next;
                len2--;
            } else {
                sum = p.val + q.val;
                p = p.next;
                q = q.next;
                len1--;
                len2--;
            }
            ListNode node = new ListNode(sum);
            node.next = tempHead;
            tempHead = node;
        }

        ListNode dummyResult = new ListNode(1);
        int carry = 0;
        while (tempHead != null) {
            ListNode node = tempHead;
            tempHead = tempHead.next;

            node.val += carry;
            carry = node.val / 10;
            node.val %= 10;

            node.next = dummyResult.next;
            dummyResult.next = node;
        }

        if (carry == 1) {
            return dummyResult;
        }
        return dummyResult.next;
    }
}

/**
 * Using stack.
 *
 * Time Complexity: O(M + N)
 *
 * Space Complexity: O(M + N)
 *
 * M = Number of nodes in l1. N = Number of nodes in l2.
 */
class Solution2 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        ListNode p = l1;
        ListNode q = l2;

        while (p != null) {
            stack1.push(p.val);
            p = p.next;
        }
        while (q != null) {
            stack2.push(q.val);
            q = q.next;
        }

        ListNode dummyHead = new ListNode(1);
        int carry = 0;

        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            int sum = carry;
            sum += !stack1.isEmpty() ? stack1.pop() : 0;
            sum += !stack2.isEmpty() ? stack2.pop() : 0;

            ListNode node = new ListNode(sum % 10);
            carry = sum / 10;

            node.next = dummyHead.next;
            dummyHead.next = node;
        }

        if (carry == 1) {
            return dummyHead;
        }
        return dummyHead.next;
    }
}

/**
 * Recursive Solution
 *
 * Time Complexity: O(M + N)
 *
 * Space Complexity: O(max(M, N))
 *
 * M = Number of nodes in l1. N = Number of nodes in l2.
 */
class Solution3 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode p = l1;
        ListNode q = l2;
        int len1 = 0;
        int len2 = 0;

        while (p != null) {
            len1++;
            p = p.next;
        }
        while (q != null) {
            len2++;
            q = q.next;
        }

        ListNode dummyHead = new ListNode(1);

        int carry = addTwoNumbersHelper(dummyHead, l1, len1, l2, len2);
        if (carry == 1) {
            return dummyHead;
        }
        return dummyHead.next;
    }

    private int addTwoNumbersHelper(ListNode sumListHead, ListNode p, int lenP, ListNode q, int lenQ) {
        if (lenP == 0 && lenQ == 0) {
            return 0;
        }

        int sum = 0;

        if (lenP > lenQ) {
            sum = addTwoNumbersHelper(sumListHead, p.next, lenP - 1, q, lenQ);
            sum += p.val;
        } else if (lenP < lenQ) {
            sum = addTwoNumbersHelper(sumListHead, p, lenP, q.next, lenQ - 1);
            sum += q.val;
        } else {
            sum = addTwoNumbersHelper(sumListHead, p.next, lenP - 1, q.next, lenQ - 1);
            sum += p.val + q.val;
        }

        ListNode node = new ListNode(sum % 10);
        node.next = sumListHead.next;
        sumListHead.next = node;
        return sum / 10;
    }
}