Add Two Numbers Ii - Leetcode Solution

Problem Statement

The problem statement for "Add Two Numbers II" on Leetcode is as follows:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, 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:

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

Explanation: 3427 + 465 = 3892, which is represented in the output as [7,8,0,7] in reverse order.

Solution

The problem statement asks us to add two numbers represented in the form of a linked list. The linked list represents the digits in reverse order, meaning that the ones digit is the head of the list, followed by the tens digit, followed by the hundreds digit, and so on.

To add the two numbers, we first need to reverse the input linked lists. We can use a stack to store the nodes of both linked lists in reverse order, and then pop the nodes one by one to compute the sum. We will keep adding the values of the nodes along with the carry carry over from the previous sum.

We can implement the above plan using the following algorithm:

• Initialize two stacks to store the nodes of the input linked lists. Traverse both linked lists and push the nodes onto their respective stacks.
• Create a dummy Node with a value of 0 and initialize carry to 0.
• Pop the top nodes from both the stacks (or if the stack is empty, use a value of 0). Add the values of both nodes along with the carry, and update the carry as the sum of the two node values divided by 10.
• Create a new node with the value equal to the sum of the two nodes modulo 10 and set this node as the next of the dummy node.
• Move the dummy node to the next position and repeat steps 3-4 until both stacks are empty.
• Return the next of the dummy node, which is the head of the reversed output linked list.

Time Complexity

The time complexity of the above algorithm is O(n), where n is the length of the longer linked list.

Space Complexity

The space complexity of the above algorithm is O(n), where n is the length of the longer linked list, as we are using two stacks to store the linked lists.

Code

Here's the python implementation for the above algorithm:

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        stack1, stack2 = [], []
        dummy = ListNode(0)
        carry = 0
        
        while l1:
            stack1.append(l1)
            l1 = l1.next
        
        while l2:
            stack2.append(l2)
            l2 = l2.next
        
        while stack1 or stack2 or carry:
            val1 = stack1.pop().val if stack1 else 0
            val2 = stack2.pop().val if stack2 else 0
            carry, val = divmod(val1 + val2 + carry, 10)
            curr = ListNode(val)
            curr.next = dummy.next
            dummy.next = curr
        
        return dummy.next

1