algoadvance

Leetcode 445. Add Two Numbers II

Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first, and each node 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

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]

Clarifying Questions:

  1. Are the input linked lists always guaranteed to be non-empty?
  2. Can the linked lists have different lengths?
  3. Do we need to consider the sign of the integers?
  4. Is there a limit to the size of the linked list?

Strategy

  1. Convert the linked lists to stacks to reverse the order, making the least significant digit come first.
  2. Pop from both stacks to add the numbers digit by digit.
  3. Handle carry for digits that sum up to more than 9.
  4. Construct a new linked list from the result.

Code

Here’s the Java code to solve the problem:

import java.util.Stack;

public class Solution {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        
        // Push all elements from l1 to stack1
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        
        // Push all elements from l2 to stack2
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        
        ListNode head = null;
        int carry = 0;
        
        // While there are elements in either stack or carry is non-zero
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int sum = carry;
            
            if (!stack1.isEmpty()) {
                sum += stack1.pop();
            }
            
            if (!stack2.isEmpty()) {
                sum += stack2.pop();
            }
            
            carry = sum / 10;
            int val = sum % 10;
            
            ListNode node = new ListNode(val);
            node.next = head;
            head = node;
        }
        
        return head;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode l1 = new ListNode(7);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        l1.next.next.next = new ListNode(3);
        
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        ListNode result = solution.addTwoNumbers(l1, l2);

        while (result != null) {
            System.out.print(result.val);
            if (result.next != null) {
                System.out.print("->");
            }
            result = result.next;
        }
    }
}

Explanation

  1. Use two stacks to capture the digits of both linked lists.
  2. Iterate through the linked lists and push each digit onto its respective stack.
  3. Create a variable carry that’s initialized to 0 to keep track of the carry-over value during addition.
  4. While there are digits to process in either stack or there is a carry-over, pop values from both stacks, add them together with the carry, and compute the new carry and current digit.
  5. Prepend the computed digit to a new linked list.
  6. Continue this process until all digits and carry have been processed.
  7. Return the head of the new linked list.

Time Complexity

The time complexity for this solution is O(n + m), where n and m are the lengths of the two input linked lists. This is because we traverse each list once to push the digits onto their respective stacks and then process each stack, which involves another traversal.

The space complexity is also O(n + m) for the stacks and the new linked list used to store the result.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI