Add Two Numbers LeetCode Solution

2.2 Pseudocode

• Initialize the current node to the dummy head of the returning list.
• Initialize carry to 0.
• Initialize p and q to the head of l1 and l2 respectively.
• Loop through lists l1 and l2 until you reach both ends.
  • Set x to the node p‘s value. If pp has reached the end of l1, set to 0.
  • Set y to node q‘s value. If q has reached the end of l2, set to 0.
  • Set sum = x+y+carry.
  • Update carry=sum/10.
  • Create a new node with the digit value of (sum mod 10) and set it to the current node’s next, then advance the current node to the next.
  • Advance both p and q.
• Check if carry=1, if so append a new node with digit 1 to the returning list.
• Return the dummy head’s next node.

3. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Linked List Traversal”. This pattern involves iterating through one or more linked lists, performing operations on their nodes, and constructing a new linked list as a result. 

4. How the Code Works

1. The goal of the code is to add two numbers represented as linked lists, where each node contains a single digit. The digits are stored in reverse order, meaning the least significant digit comes first.
2. The code iterates through both linked lists (l1 and l2) simultaneously, adding corresponding digits along with any carry from the previous addition.
3. If one list is shorter, the missing digits are treated as 0.
4. A new linked list is constructed to store the result, with each node containing the sum of the corresponding digits modulo 10. The carry (if any) is propagated to the next iteration.
5. If there is a carry left after processing all nodes, it is added as a new node at the end of the result list.

5. Code Implementation in Different Languages

5.1 Add Two Numbers C++

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int sum=0;
        ListNode *l3=NULL;
        ListNode **node=&l3;
        while(l1!=NULL||l2!=NULL||sum>0)
        {
            if(l1!=NULL)
            {
                sum+=l1->val;
                l1=l1->next;
            }
            if(l2!=NULL)
            {
                sum+=l2->val;
                l2=l2->next;
            }
            (*node)=new ListNode(sum%10);
            sum/=10;
            node=&((*node)->next);
        }        
        return l3;
    }
};

5.2 Add Two Numbers Java

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

5.3 Add Two Numbers JavaScript

var addTwoNumbers = function(l1, l2) {
    let node = null
    const carry = arguments[2]
    if (l1 || l2) {
        const val1 = l1 ? l1.val : 0
        const val2 = l2 ? l2.val : 0
        const next1 = l1 ? l1.next : null
        const next2 = l2 ? l2.next : null
        const val = carry ? val1 + val2 + 1 : val1 + val2
        node = new ListNode(val % 10)
        node.next = addTwoNumbers(next1, next2, val >= 10)  
    } else if (carry) {
        node = new ListNode(1)
        node.next = null
    }
    return node
};

5.4 Add Two Numbers Python

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        result = ListNode(0)
        result_tail = result
        carry = 0
                
        while l1 or l2 or carry:            
            val1  = (l1.val if l1 else 0)
            val2  = (l2.val if l2 else 0)
            carry, out = divmod(val1+val2 + carry, 10)    
                      
            result_tail.next = ListNode(out)
            result_tail = result_tail.next                      
            
            l1 = (l1.next if l1 else None)
            l2 = (l2.next if l2 else None)
               
        return result.next