Leetcode – 2 – Add Two Numbers

Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Description:

The problem states that two non negative numbers to be added in a linked list

Brute Force Solution: (Traverse and add the sum to new node)

On seeing this problem we will immediately think of adding the head element of the two given list and traverse till the end. The catch here is that we will have to create a third list and keep adding the values to the next elements

The third list should have its head stored so that we have to return the head of the constructed list

Some cases to be considered

  • Handling carry
  • Handling unequal lists

With all this we can come up with

  • Have a dummy node to store the head of the result node, newList so that while returning we can simply return newList.next
  • Have a running pointer p3 point to the newList.
  • Traverse for all the elements of list 1 & list 2 and compute the carry [p1, p2]
  • Take modulo of the carry and store as the new elements of the newList
  • Store the carry as the last element if it is set

1

Code:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode newList = new ListNode(0);
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode p3 = newList;
        int carry = 0;
        
        while(p1 != null || p2 != null){
            
            if(p1 != null){
                carry = carry + p1.val;
                p1 = p1.next;
            }
            
            
            if(p2 != null){
                carry = carry + p2.val;
                p2 = p2.next;
            }
            
            p3.next = new ListNode(carry % 10);
            p3 = p3.next;
            carry = carry / 10;
        }
        
        if(carry == 1){
            p3.next = new ListNode(1);
        }
        
        return newList.next;
    }

Time Complexity: O(m + n)

  • we are simply traversing m elements in list 1 and n elements in list 2 – O(m + n)

Space Complexity:O(n)

  • you will end up creating n nodes for the new list – O(n)

Available Test Cases: 1555

  • Check for null input list
  • Check for zero elements
  • Check for unequal lists
  • Check for overflow
  • Check of underflow
  • Check with duplicate elements
  • Check for carry logic

 Github:

Leetcode_2_Add_Two_numbers_in_list

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: