Find sum of two numbers stored in linked list and store result in another linked list

Problem statement:- Two numbers 345 and 928 are stored in linked list (each digit as single node). We need to find sum of these two number and store the summation in some other liked list.Refer following for

 /* Two numbers stored in linked lists 
   *           3 --> 4 --> 5--> 1
   *  4-->2-->9 --> 2 --> 8 -->3
   * Result(Sum stored in linked list) : 4-->3-->2-->7-->3-->4 
*/

Algorithm :-
1. First, reverse the given two linked list,since sum of two number can be performed from right side and we have access of left most node using head of two linked lists. Once we reverse the linked list,we have control over last node and we can perform sum operation. Refer How to reverse a liked list
2. Do sum operation and store carry in some temporary variable, if comes out, and add it in next nodes sum.
3. Create a new node for the storing result of sum of two nodes.
4. Repeat step 2 and until both liked list are not empty.
5. If any one of the linked list is empty, directly add all remaining elements of another list in result linked list.
6. Finally reverse the linked list which is storing result of sum.

private Node sumOfTWoLinkedlist(Node head1, Node head2) {
 Node resultHead = null;
 int carry = 0;
 int temp;
 /* Reverse both linked list */
 head1 = reverseLinkedListUsingRecursion(head1);
 head2 = reverseLinkedListUsingRecursion(head2);
 /* Traverse both linked list until either one of list is not null */
 while (head1 != null && head2 != null) {
  temp = head1.data + head2.data;
  /* If carry is there add with temp */
  if (carry != 0)
   temp += carry;
  /* Compute new carry and node data */
  carry = temp / 10;
  temp = temp % 10;

  // create a new node and append in result linked list
  resultHead = createAndAppendNodeInResultList(resultHead, temp);
  head1 = head1.next;
  head2 = head2.next;
 }
 /*
  * One of the list reached at end and another one having elements left,
  * do copy of remaining to result linked list
  */
 if (head1 != null) {// Check whether List 1 has extra elements
  // copy elements directly to result linked list
  while (head1 != null) {
   temp = carry + head1.data;
   carry = temp / 10;
   temp = temp % 10;
   createAndAppendNodeInResultList(resultHead, temp);
   head1 = head1.next;
  }
 } else if (head2 != null) {// Check whether List 2 has extra elements
  // copy elements directly to result linked list
  while (head2 != null) {
   temp = carry + head2.data;
   carry = temp / 10;
   temp = temp % 10;
   createAndAppendNodeInResultList(resultHead, temp);
   head2 = head2.next;
  }

 } else {
  createAndAppendNodeInResultList(resultHead, carry);
 }
 //Check if carry is zero or not, if not zero add in result list
 if (carry != 0) {
  createAndAppendNodeInResultList(resultHead, carry);
 }
 // Reverse result linked list to obtain expected outcome
 resultHead = reverseLinkedListUsingRecursion(resultHead);
 return resultHead;
}

Explanation:- First traverse both linked lists until we encounter null in any linked list. Then , copy remaining elements in result linked list depending on which linked list has more elements. Before copying elements in while loop, settle carry with linked list data and store it in result linked list. Once copying of elements are complete, reverse the linked list and return head of new result linked list.

Time and space complexity :- Since each node of  both linked list is visited only once so time complexity is O(n) and space complexity is O(max(m,n)) - result linked list space.
Below is the complete sample program for finding sum of two numbers stored in linked list.

package com.devinline.linkedlist;

public class SumOfTwoLinkedList {

private Node sumOfTWoLinkedlist(Node head1, Node head2) {
 Node resultHead = null;
 int carry = 0;
 int temp;
 /* Reverse both linked list */
 head1 = reverseLinkedListUsingRecursion(head1);
 head2 = reverseLinkedListUsingRecursion(head2);
 /* Traverse both linked list until either one of list is not null */
 while (head1 != null && head2 != null) {
  temp = head1.data + head2.data;
  /* If carry is there add with temp */
  if (carry != 0)
   temp += carry;
  /* Compute new carry and node data */
  carry = temp / 10;
  temp = temp % 10;

  // create a new node and append in result linked list
  resultHead = createAndAppendNodeInResultList(resultHead, temp);
  head1 = head1.next;
  head2 = head2.next;
 }
 /*
  * One of the list reached at end and another one having elements left,
  * do copy of remaining to result linked list
  */
 if (head1 != null) {// Check whether List 1 has extra elements
  // copy elements directly to result linked list
  while (head1 != null) {
   temp = carry + head1.data;
   carry = temp / 10;
   temp = temp % 10;
   createAndAppendNodeInResultList(resultHead, temp);
   head1 = head1.next;
  }
 } else if (head2 != null) {// Check whether List 2 has extra elements
  // copy elements directly to result linked list
  while (head2 != null) {
   temp = carry + head2.data;
   carry = temp / 10;
   temp = temp % 10;
   createAndAppendNodeInResultList(resultHead, temp);
   head2 = head2.next;
  }

 } else {
  createAndAppendNodeInResultList(resultHead, carry);
 }
 //Check if carry is zero or not, if not zero add in result list
 if (carry != 0) {
  createAndAppendNodeInResultList(resultHead, carry);
 }
 // Reverse result linked list to obtain expected outcome
 resultHead = reverseLinkedListUsingRecursion(resultHead);
 return resultHead;
}

 private Node createAndAppendNodeInResultList(Node head, int data) {
  return head = insertLast(head, data);
 }

 private Node createNewNode(int data) {
  return new Node(data);
 }

 /* Iterate linked list, reach at end and add new node */
 private Node insertLast(Node head, int data) {
  Node newNode = createNewNode(data);
  Node current = head;
  if (head == null) {
   head = newNode;
  } else {
   while (current.getNext() != null) {
    current = current.getNext();
   }
   current.setNext(newNode);
   newNode.setNext(null);
  }
  return head;
 }

 /*
  * Reverse a singly linked list using recursion Reference :-
  * http://coding-injava
  * .blogspot.in/2014/02/reverse-singly-linked-list-in-java.html
  */
 static public Node reverseLinkedListUsingRecursion(Node head) {
  /* Return null , if list is empty or head if head.next = null */
  if (head == null || head.getNext() == null) {
   return head;
  } else {
   /* Store next node of list */
   Node nextNode = head.getNext();
   /* For storing reference of last node of list */
   Node retHead = reverseLinkedListUsingRecursion(nextNode);
   /* Set next reference of the given node to null, breaking the chain */
   head.setNext(null);
   /* Add next reference in reverse order */
   nextNode.setNext(head);
   /* Return last node of the given list */
   return retHead;
  }
 }

 class Node {

  private int data;
  private Node next; // reference(handler) for next Node.

  public Node(int data) {
   this.data = data;
   this.next = null;
  }

  public Node getNext() {
   return next;
  }

  public void setNext(Node next) {
   this.next = next;
  }

  public int getData() {
   return data;
  }
 }

 /* Display data of nodes/iterate linked list */
 private static void displayLinkedlist(Node head) {
  Node current = head;
  if (head != null) {
   System.out.print("Data in linkedlist:[");
   while (current != null) {
    System.out.print(current.getData() + " ");
    current = current.getNext();
   }
   System.out.print(" ]\n");
  } else {
   System.out.println("Linked list is empty.");
  }

 }

 public static void main(String[] args) {
  Node head1;
  Node head2;
  /* First linked list fomation */
  SumOfTwoLinkedList sol = new SumOfTwoLinkedList();
  Node node1 = sol.new Node(3);
  head1 = node1;
  Node node2 = sol.new Node(4);
  Node node3 = sol.new Node(5);
  Node node4 = sol.new Node(1);
  head1.next = node2;
  head1.next.next = node3;
  head1.next.next.next = node4;

  /* Second linked list fomation */
  Node node12 = sol.new Node(4);
  head2 = node12;
  Node node22 = sol.new Node(2);
  Node node32 = sol.new Node(9);
  Node node42 = sol.new Node(2);
  Node node52 = sol.new Node(8);
  Node node62 = sol.new Node(3);
  head2.next = node22;
  head2.next.next = node32;
  head2.next.next.next = node42;
  head2.next.next.next.next = node52;
  head2.next.next.next.next.next = node62;
  System.out.print("Linked list -1  ");
  displayLinkedlist(head1);
  System.out.print("Linked list -2  ");
  displayLinkedlist(head2);
  Node resultNode = sol.sumOfTWoLinkedlist(head2, head1);
  System.out.print("Sum of two list ");
  displayLinkedlist(resultNode);
 }

}

==========Sample output==============
Linked list -1  Data in linkedlist:[3 4 5 1  ]
Linked list -2  Data in linkedlist:[4 2 9 2 8 3  ]
Sum of two list Data in linkedlist:[4 3 2 7 3 4  ]
===================================