Add Two Numbers as Lists - Interview Problem

Difficulty: Medium

Asked in: Amazon, Microsoft, Facebook

Understanding the Problem

Problem Description: 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 it as a linked list.

For Example:

Input: (1 -> 8-> 2) + (3 -> 6 -> 5)
Output: (4-> 4-> 8)
Explanation: 281+ 563= 844.

Input: (4 -> 8-> 1) + (3 -> 6 )
Output: 7-> 4-> 2
Explanation: 184+ 63= 247

The node structure for the Linked List passed to your function will be

class Node {
    int val
    Node *next
    
    Node(int v)
    {
        val = v
        next = NULL
    }
}

Possible follow-up questions to ask the interviewer:-

• Is it possible that both linked lists are of different sizes? (Ans: Yes)
• Is there any, possibility that there can be leading zeros in linked lists? (Ans: You may assume the two numbers do not contain any leading zero, except the number 0 itself.)

Solution

How do we add two numbers in real life? First, we add the digits at a unit place in both numbers and if it is greater than 10, we take a carry as 1 and place the unit digit of the sum in the unit place of the answer. We continue this process for the remaining places.

Solution idea

We will do the same if the numbers are in the form of a linked list. The idea is to traverse both linked lists and pick the nodes of both lists one by one and add them. We need to implement the concept of carrying too in our code.

We need to consider some cases that can happen during the iteration

• Size of linked lists are different - There will be a time in the iteration where there will not be further nodes left in one linked list, then we will just run through the other and maintain the carry if possible.
• An extra node is required for storing the final carry in output - Let us suppose we have an example for adding (9->9) + (1->1). The output will be 0->1->1. So there can be a possibility that one extra node is required for the output.

Solution Steps

1. Initialize head and curr to NULL which will store the head and the current node of the output list respectively.
2. Initialize carry to 0.
3. Iterate the linked list till one reaches the end.

• Add the values of the nodes with carry.
• Generate carry and find the unit place of sum.
• Now if the head is NULL, add the first node in the output linked list and also assign curr = head.
• If head is not NULL, then append new node in curr.next and make curr pointing to new node ie curr = curr.next.

4. Now, there might be a case that one linked list is not fully iterated so, again iterate through that list and add carry and node's value and generate sum and append this new node of the sum to curr.next and move curr to new node.

5. There might be a condition that both linked list are fully iterated but there is carry generated, so append this carry at the end of linked list

6. Return head.

Pseudo-Code

Node addTwoNumberInLists(Node A, Node B)
{
    Node head = NULL, curr = NULL
    int carry = 0
    
    while( (A!= NULL) && (B!= NULL) )
    {
        int s = A.val + B.val + carry
        
        carry = s / 10    // Ten's place, becomes 0 if s < 10
        s = s % 10        // Unit's place 
        
        if( head == NULL )
        {
            head = Node(s)
            curr = head
        }
        else
        {
            curr.next = Node(s)
            curr = curr.next
        }
        A = A.next
        B = B.next
    }

    while ( A != NULL )
    {
        int s = A.val + carry
        carry = s / 10
        s = s % 10
        curr.next = Node(s)
        curr = curr.next
        A = A.next
    }

    while( B != NULL )
    {
        int s = B.val + carry
        carry = s / 10
        s = s % 10
        curr.next = Node(s)
        curr = curr.next
        B = B.next
    }

    if( carry != 0 )
        curr.next = Node(carry)

    return head
}

Complexity Analysis

Time Complexity: O(M+N), where M and N are the lengths of two linked lists.

Space Complexity: O(1)

Critical ideas to think!

• Try solving this problem using recursion.
• How would you solve this question if the head is pointed to the most significant digit?

Suggested problems to solve

• Add 1 to a number represented as a linked list.
• Subtract two numbers represented as linked lists.
• Compare two strings represented as linked lists
• Multiply two numbers represented by linked lists.

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

May the code be with You!

Enjoy Algorithms!

AfterAcademy Data Structure And Algorithms Online Course - Admissions Open