Add Two Numbers

Back to home
Logicmojo - Updated March 28, 2022



Problem Statement: Add Two Numbers

Two non-empty linked lists representing two non-negative integers are given to you. The digits are kept in reverse order, with a single digit in each of their nodes. Return the sum as a linked list after adding the two numbers.

Input 1 :
firstList = [3,1,2]
secondList = [4,7,6]
Output 1 : [7,8,8]
Explanation : 312 + 476 = 788.

Input 2 :
firstList = [7,5,9,4,6]
secondList = [8,4]
Output 2: [5,0,0,5,6]

Crack your next tech interview with confidence!
Explanation 2:
The resultant linked-list is 5 -> 0 -> 0 -> 5 -> 6. Adding the linked lists in the above manner with the laws of sum and carry of addition gives us 5 -> 0 -> 0 -> 5 -> 6.


Approach

This is how we address the challenge. We'll traverse both lists and append zeros to the list with the less digits until both integers have the same number of digits. Then we may recursively begin at the beginning nodes of both lists, and the function will go forward on both lists until we reach the end. We'll keep generating new nodes to store the sum of the digits as we recurse, and the recursive function will return the carry to the next node for the sum operation.

Algorithm

  1. Perform a traverse on both linked lists and append zeros to the end of the shorter list to make it the same length as the large list.

  2. Start a recursive function from the start nodes of both the lists, where the function will further call the next nodes of the list.

  3. The recursion continues till we reach the end of a linked list.

  4. We'll keep adding new nodes to record the sum of digits of our result as we continue our recursion, and the recursive function will return the carry to the next step in each recursive call.

C++ Implementation:

// class Node {
// public:
//     int data;
//     Node* next;
// };
Node * addTwoLists(Node * first, Node * second) {
  Node * res = NULL;
  Node * temp;
  Node * prev = NULL;
  int carry = 0, sum = 0;
  while (first != NULL || second != NULL) {
    sum = carry;
    sum += first != NULL ? first -> data : 0;
    sum += second != NULL ? second -> data : 0;
    if (sum >= 10) {
      carry = 1;
    } else {
      carry = 0;
    }
    sum %= 10;
    temp = newNode(sum);
    if (res != NULL) {
      prev -> next = temp;
    } else {
      res = temp;
    }
    prev = temp;
    if (first) {
      first = first -> next;
    }
    if (second) {
      second = second -> next;
    }
  }

  if (carry > 0)
    temp -> next = newNode(carry);
  return res;
}

Node * reverse(Node * head) {
  if (head == NULL || head -> next == NULL) {
    return head;
  }
  Node * rest = reverse(head -> next);
  head -> next -> next = head;
  head -> next = NULL;
  return rest;
}

Node * solve(Node * list1, Node * list2) {
  list1 = reverse(list1);
  list2 = reverse(list2);
  Node * added = addTwoLists(list1, list2);
  return added;
}


Java Implementation:

/*
static class Node {
    int data;
    Node next;
    
    Node(int d) {
        data = d;
        next = null;
    }
}
*/
public static Node addTwoLists(Node first, Node second) {
  Node start1 = new Node(0);
  start1.next = first;
  Node start2 = new Node(0);
  start2.next = second;
  addPrecedingZeros(start1, start2);
  Node result = new Node(0);
  if (sumTwoNodes(start1.next, start2.next, result) == 1) {
    Node dummy = new Node(1);
    dummy.next = result.next;
    result.next = dummy;
  }
  return result.next;
}
public static int sumTwoNodes(Node first, Node second, Node result) {
  if (first == null) {
    return 0;
  }
  int sum = 0;
  sum += first.data;
  sum += second.data;
  sum += sumTwoNodes(first.next, second.next, result);
  Node dummy = new Node(sum % 10);
  dummy.next = result.next;
  result.next = dummy;
  return sum / 10;
}
public static void addPrecedingZeros(Node start1, Node start2) {
  Node next1 = start1.next;
  Node next2 = start2.next;
  while (next1 != null && next2 != null) {
    next1 = next1.next;
    next2 = next2.next;
  }
  if (next1 == null) {
    if (next2 != null) {
      while (next2 != null) {
        Node dummy = new Node(0);
        dummy.next = start1.next;
        start1.nedummy dummy;
        next2 = next2.next;
      }
    }
  } else if (next2 == null) {
    if (next1 != null) {
      while (next1 != null) {
        Node dummy = new Node(0);
        dummy.next = start2.next;
        start2.next = dummy;
        next1 = next1.next;
      }
    }
  }
}
public static Node solve(Node first, Node second) {
  Node result = addTwoLists(first, second);
  return result;
}


Python Implementation:

# class Node:

#     def __init__(self, data):
#         self.data = data
#         self.next = None
def addTwoLists(self, first, second):
    prev = None
    temp = None
    carry = 0
    while first is not None or second is not None:
        if first is None:
            firstData = 0
        else:
            firstData = first.data
        if second is None:
            secondData = 0
        else:
            secondData = second.data
        Sum = carry
        Sum += firstData
        Sum += secondData
        if Sum >= 10:
            carry = 1
        else:
            carry = 0
        Sum %= 10
        temp = Node(Sum)
        if self.head is None:
            self.head = temp
        else:
            prev.next = temp
        prev = temp
        if first is not None:
            first = first.next
        if second is not None:
            second = second.next
    if carry > 0:
        temp.next = Node(carry)


Time Complexity: O(n + m),
where, n = length of 1st list, m = length of 2nd list.

Space Complexity: O(n + m),
Temporary linked list needed to store results in form of dummy node.



With this article at Logicmojo, you must have the complete idea of add two numbers problem.
© 2020 Logicmojo. ALL RIGHTS RESERVED