Add Two Numbers — Leetcode 2

  • Post last modified:November 7, 2022
  • Reading time:3 mins read

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.

Further Reading

Follow me on Medium & LinkedIn

Leave a Reply