Blog

Introduction

• In this article, we will solve Leetcode problem #2 which is good to learn and operate on Linked List.

Problem Statement

• We have been given two non-empty LinkedList that represents non-negative integers.
• Digits are stored in reverse order and doesn’t contain any leading zeros.
• We need to add these two numbers and return the result as LinkedList.

Examples

• In below example we can are adding 2+5 = 7, 4+6 = 10, 3+4+1(carry) = 8
  hence we need to return the result as [7,0,8]

Solutions

Intuition

• The institution is simple that we will traverse two LinkedList simultaneously. 
• If both the list are null then we don’t have anything to add so we can break out of the loop.
• But if one of them is null then we can safely assume 0 as the value and add that to another list.

• While doing so we will add two-digit and check if it’s greater than or equal to 10. If it’s greater than 10 then we can assign carry as 1 and the value of sum would be sum mod 10 -> sum%10.
• We assign the resultnode with the sum value and add it to the result list.

• We will keep creating new nodes for the sum and add to the result in LinkedList that we will create at the start of the program.

• Once we have traversed both the list that means both list are null then we still need to check if there is carry which is non-zero, if that is the case then our last addition end with 1 carry. hence we need to add that to our result list.

• Now we can result in a dummy. next as the head of the result list since the dummy node has a reference to head of the result list and result list itself reached to the end because of traversal and we cannot use it.

Code

• Our entire code looks like below

ublic ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode();
        ListNode dummy = res;
        int carry = 0;
        while(true){
           if(l1==null && l2==null){
             break;  
           }
           if(l1==null) l1=new ListNode(0);
           if(l2==null) l2=new ListNode(0);
           int sum = l1.val + l2.val + carry;
           carry = 0;
           if(sum>=10) {
               carry = 1;
               sum%=10;
           }
           res.next = new ListNode(sum);
           res = res.next;
           l1 = l1.next;
           l2 = l2.next;
        }
        
        if(carry>0){
            res.next = new ListNode(carry);
            res = res.next;
        }

        return dummy.next;
        
    }

Result

• Our code is accepted by the platform

Complexity

• Time Complexity : O(max(m,n)) where m and n are lengths of two nodes.
• Space Complexity: O(max(m,n)) the length of result is max(m,n)+1

Conclusion

• In this leetcode problem we learned about Linkedlist operation and discuss how we can construct and traverse LinkedList to perform arithmetic operations such as addition.

Bonus Tip

• If you want to upskill your coding interview game, you can definitely check out this bestseller course ( this is in Java )

Further Reading

• https://asyncq.com/category/dsa

Follow me on Medium & LinkedIn