Add Two Integers

editor-page-cover

Problem Statement

Given the head pointers of two linked lists where each linked list represents an integer number (each node is a digit), add them and return the resulting linked list. Here, the first node in a list represents the least significant digit.

widget

Hint

  • Handle carry

Try it yourself

LinkedListNode* add_integers(
    LinkedListNode* integer1, 
    LinkedListNode* integer2) {
  //TODO: Write - Your - Code
  return integer1;
}

Solution

// assuming both integers are stored in a linked list
// e.g. 415 is stored as 5->1->4
// 32 is stored as 2->3
LinkedListNode* add_integers(
    LinkedListNode* integer1, 
    LinkedListNode* integer2) {

  LinkedListNode* result = nullptr;
  LinkedListNode* last = nullptr;
  int carry = 0;
  
  while (
      integer1 != nullptr ||
      integer2 != nullptr ||
      carry > 0) {

    int first = 
        (integer1 == nullptr ? 0 : integer1->data);
    int second = 
        (integer2 == nullptr ? 0 : integer2->data);

    int sum = first + second + carry;

    LinkedListNode* pNew = 
          new LinkedListNode(sum % 10);
    
    carry = sum / 10;

    if (result == nullptr) {
      result = pNew;
    } else {
      last->next = pNew;
    }

    last = pNew;
    
    if (integer1 != nullptr) {
      integer1 = integer1->next;
    }
    
    if (integer2 != nullptr) {
      integer2 = integer2->next;
    }
  }
  
  return result;
}

int main(int argc, char* argv[]) {
	vector<int> v1 = {1, 2, 3}; // 321
  vector<int> v2 = {1, 2}; // 21
  
  LinkedListNode* first = LinkedList::create_linked_list(v1);
  LinkedListNode* second = LinkedList::create_linked_list(v2);

  // sum should be 321 + 21 = 342 => 2->4->3
  LinkedListNode* result = add_integers(first, second);
  vector<int> r = {2, 4, 3}; // 342
  LinkedListNode* expected = LinkedList::create_linked_list(r);
  assert(LinkedList::is_equal(result, expected));

  cout << endl << "First:";
  LinkedList::display(first);
  cout << endl << "Second:";
  LinkedList::display(second);
  cout << endl << "Result:";
  LinkedList::display(result);

  result = add_integers(first, nullptr);
  assert(LinkedList::is_equal(result, first));

  result = add_integers(nullptr, second);
  assert(LinkedList::is_equal(result, second));
}

Solution Explanation

Runtime Complexity

Linear, O(n)

Runtime complexity is based on the length of the linked lists.

Memory Complexity

Linear, O(n)


Solution Breakdown

For a better understanding of the problem, let’s take a look at an example. Suppose we want to add the integers 9901 and 237. The result of this addition would be 10138.

The integers are stored inverted in the linked lists to make the addition easier. Now, the most significant digit of the number is the last element of the linked list. For the addition, we’ll start from the heads of the two linked lists. At each iteration, we add the current digits of the two lists and insert a new node with the resulting digit at the tail of the result linked list. We’ll also need to maintain carry at each step. We’ll keep doing this for all digits in both the linked lists. If one of the linked lists ends sooner, we’ll continue with the other linked list. Once both of the linked lists are exhausted, and no carry is left to be added, the algorithm will terminate.