Add Two Numbers Represented by Linked Lists

Problem Statement

Given 2 numbers, where each digit is represented by nodes of a LinkedList, find the sum of the 2 numbers represented as LinkedList.

Sample Test Cases

Input 1:
firstList = 7 5 9 4 6
secondList = 8 4

Output 1: result = 5 0 0 5

Adding the linked lists in the above manner with the rules of sum and carry of addition, we get the resultant linked-list as 5 -> 0 -> 0 -> 5 -> 6.

Input 2:
firstList = 0
secondList = 0
Output 2:
result = 0

Explanation 2:
Both the linked lists in the above example represent the number 0, so the result is also a single node with the value 0.

Approach
We approach this problem as follows. We will perform a traversal on both the lists and append zeros on the list which has a lesser number of digits till both numbers have an equal number of digits. Then we can recursively start from the start nodes of both the lists, where the function recursively moves ahead on both the lists till we reach the end. In the process of recursion, we will keep creating new nodes which will store the sum of the digits, and the recursive function returns the carry onto the next node for the sum operation.
The algorithm is as described below:

Perform a traversal on both the linked lists and make the shorter list of length equal to the long list by appending zeros to its end.

Start a recursive function from the start nodes of both the lists, where the function will further call the next nodes of the list.
The recursion continues till we reach the end of a linked list.
While continuing our recursion, we will keep adding new nodes which will store the sum of digits of our result, and the recursive function will return the carry to the next step in each recursive call.
Run the code with InterviewBit's Online C++ Compiler

C++ Code

// 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 Code

/*
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;
}