Apr 27, 2014

Implement a Stack using two Queues in Java

Stack is an abstract data structure with property of  Last In First Out as contrast to queue - First In First Out.In order to implement stack using queue we have to choose between which operation do we want to make costly - push() or pop(), push() operation of stack is associated with enQueue() operation of queue and pop() operation is associated with dequeue().The fundamental concept is same as we discussed in Implementing Queue using two Stack.

Algorithm:-
 
1. Two Queues are used to implement Stack, for push() operation elements are pushed into queue-1 and for pop() operation elements are popped from queue-2 (push n-1 elements from queue-1 in queue-2 and return nth element as return of pop()).
2. push() operation is of order O(1) as elements are added at end and we do not have to traverse whole list for insertion(reference last is maintained by implementing linked list) and pop() operation is of order O(n) as in each operation elements are transferred between q1 and q2.
3. As queue is an abstract data structure,it can be implemented using singly linked list or array, here linked list has been used. 
/* Insert into q1 - push operation is order of O(1) */
public void push(int data) {
q1.enQueue(data);
}

/* Transfer N-1 elements from q1 to q2 and return last element of q1 -
pop operation is order of O(n) */
public int pop() {
int size, i = 0;
size = q1.size();
i = 0;
while (i < size - 1) {
q2.enQueue(q1.deQueue());
i++;
}
/*Store last element from q1*/
int returnVal = q1.deQueue();

/* swap q1 and q2 - It avoids transferring all elements from q2 to q1 again*/
QueueCustom tempRef;
tempRef = q1;
q1 = q2;
q2 = tempRef;

return returnVal;
}

Explanation:-
As stated earlier, push() is costly operation and pop() is of constant time, we can revert the cost of push() and pop().Here, on each pop() operation , elements from q1 is tranferred to q2 so that last inserted element is returned to caller of pop().
Swapping of references is done, in order to avoid transferring of elements from q2 to q1 , since if we do not swap then Stack's LIFO property would be violated.

Time complexity:-  push(data) operation is of order O(1) and pop() operation is of order O(n).

Complete sample program - Implement a Stack using two Queues in Java 

package com.devinline.queues;

public class CustomStackUsingtwoQueue {
QueueCustom q1;
QueueCustom q2;

public CustomStackUsingtwoQueue() {
q1 = new QueueCustom();
q2 = new QueueCustom();
}

/* Insert into q1 - push operation is order of O(1) */
public void push(int data) {
q1.enQueue(data);
}

/*
* Transfer N-1 elements from q1 to q2 and return last element of q1 - pop
* operation is order of O(n)
*/
public int pop() {
int size, i = 0;
size = q1.size();
i = 0;
while (i < size - 1) {
q2.enQueue(q1.deQueue());
i++;
}
/* Store last element from q1 */
int returnVal = q1.deQueue();

/*
* swap q1 and q2 - It avoids transferring all elements from q2 to q1
* again
*/
QueueCustom tempRef;
tempRef = q1;
q1 = q2;
q2 = tempRef;

return returnVal;
}

public int peek() {
return 0;
}

public int getSize() {
int size = 0;
if (!q1.isEmpty()) {
size += q1.size();
}
if (!q2.isEmpty()) {
size += q2.size();
}
return size;
}

public String toString() {
StringBuffer sbf = new StringBuffer();
if (!q1.isEmpty()) {
sbf.append(q1.toString());
}
if (!q2.isEmpty()) {
sbf.append(q2.toString());
}
return sbf.toString();
}
}

class SingleListImpQueue {
private Node first; // ref to first item
private Node last; // ref to last item

public SingleListImpQueue() {
first = null; // Empty list
last = null;
}

public static Node createNewNode(int data) {
return new Node(data);
}

/* get first element */
public Node getFistNode() {
if (first == null)
return null;
else
return first;
}

/* Data nodes */
public String toString() {
StringBuffer sbf = new StringBuffer();
Node current = first;
if (first != null) {
sbf.append("[");
while (current != null) {
sbf.append(current.data + " ");
current = current.next;
}
sbf.append(" ]");
} else {
System.out.println("Linked list is empty.");
}
return sbf.toString();

}

public void displayList() {
Node current = first;
while (current != null) // until end of list,
{
System.out.println(current.data);
current = current.next;
}
}

public int getSizeOfList() {
Node current = first;
int count = 0;
while (current != null) // until end of list,
{
count++;
current = current.next;
}
return count;
}

/* Delete First node,return new head */
public Node deleteFirstNode() {
if (first == null)
return null;
Node temp = first.next;
Node delNode = first;
first.next = null;// garbage collected
first = temp;
return delNode;
}

/* add elements at end of list */
public void insertLast(int data) {
Node newNode = createNewNode(data);
/* If list is empty, first node is newNode */
if (isEmpty()) {
// first --> newLink
first = newNode;
} else {
// old last --> newLink
last.next = newNode;
}
last = newNode; // newLink <-- last
}

public boolean isEmpty() {
return first == null ? true : false;
}

}

class Node {
public int data;
public Node next;

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

class QueueCustom {
private SingleListImpQueue list;

public QueueCustom() {
createQueue();
}

void createQueue() {
list = new SingleListImpQueue();
}

/* put item at rear of queue */
public void enQueue(int data) {
list.insertLast(data);
}

/* returns front element of queue and removes */
public int deQueue() {
Node temp = list.deleteFirstNode();
if (temp != null)
return temp.data;
else
return -1;
}

/* returns front element of queue without removing */
public int peekFront() {
if (list.getFistNode() != null)
return list.getFistNode().data;
return 0;
}

/* returns true if queue is empty */
public boolean isEmpty() {
return list.isEmpty();
}

/* returns number of items in queue */
public int size() {
return list.getSizeOfList();

}

public String toString() {
return list.toString();
}
}

Test Client program:-

package com.devinline.queues;

public class CustomStackUsingtwoQueueTestClient {
public static void main(String[] args) {
CustomStackUsingtwoQueue stack = new CustomStackUsingtwoQueue();
stack.push(12);
stack.push(112);
stack.push(32);
stack.push(45);
stack.push(62);
stack.push(56);
stack.push(7);
stack.push(45);
System.out.println("Stack afte 8 push() operation " + stack.toString()
+ " Current size is " + stack.getSize());
System.out.println("pop()-1 " + stack.pop());
System.out.println("pop()-2 " + stack.pop());
System.out.println("pop()-3 " + stack.pop());
System.out.println("Stack after 3 pop() operation" + stack.toString()
+ " Current size is " + stack.getSize());
stack.push(52);
stack.push(612);
stack.push(772);
stack.push(487);
stack.push(63);
stack.push(36);
System.out.println("Stack afte 6 push() " + stack.toString()
+ " Current size is " + stack.getSize());
System.out.println("pop()-1 " + stack.pop());
System.out.println("pop()-2 " + stack.pop());
System.out.println("Stack after 2 pop() operation" + stack.toString()
+ " Current size is " + stack.getSize());
}
}

=============Sample Output====================
Stack afte 8 push() operation [12 112 32 45 62 56 7 45  ] Current size is 8
pop()-1 45
pop()-2 7
pop()-3 56
Stack after 3 pop() operation[12 112 32 45 62  ] Current size is 5
Stack afte 6 push() [12 112 32 45 62 52 612 772 487 63 36  ] Current size is 11
pop()-1 36
pop()-2 63
Stack after 2 pop() operation[12 112 32 45 62 52 612 772 487  ] Current size is 9
============================================

Reference:-
http://stackoverflow.com/questions/688276/implement-stack-using-two-queues

Apr 19, 2014

Implement a queue using two stacks in Java

Queue is an abstract data structure with property of  First In First Out as contrast to stack's property First In Last Out.In order to implement queue using stack we have to choose between which operation do we want to make costly - enqueue() or dequeue(), enqueue() operation of queue is associated with push() operation of stack and dequeue() is associated with pop().

Algorithm:- 

1. Two stacks are used to implement Queue, for enQueue() operation elements are pushed into stack-1 and for deQueue() operation elements are popped from stack-2 (push elements from stack-1 if stack-2 is empty).
2. enQueue() operation is of order O(1) always and deQueue() operation is of order O(1) only if stack -2 is not empty, otherwise it will take more time(pushing elements from stack-1 to stack-2). However, number of elements transferred from stack-1 and number of elements popped from stack-2 is same, so average complexity of deQueue() operation is order of O(1).
3. Since, stack is an an abstract data structure, stack is implemented using singly linked list.

Sample code for enQueue() and deQueue operation :- 

/* Internally call push operation of order O(1) */
void enQueue(int data) {
s1.push(data);
}

/* Internally call pop operation of amortized complexity order O(1) */
int deQueue() {
int temp = -999999; // A marker value indicating empty queue
/* If S2 is not empty, return top element in O(1) */
if (!s2.isEmplty()) {
return s2.pop();
}
if (s1.isEmplty()) {
System.out.println("Queue is empty!!");
}
while (!s1.isEmplty()) {
temp = s1.peek();
s2.push(s1.pop());
}
/* Remove top element from S2 */
if (!s2.isEmplty())
s2.pop();
return temp;
}

Explanation:-
For enQueue() operation push operation is called and internally calls Linkedlist's insertFirst() operation to adds elements in stack-1.
For deQueue() operation , if stack-2 is empty , elements are transferred form  stack-1 to stack-2, otherwise elements are popped from stack-2. When stack-2 is empty, after elements transferred to stack-2, last element is removed from top.
Time complexity :- enQueue() operation of order O(1) and deQueue() operation is of amortized complexity order O(1).

Complete sample program - implementing Queue using 2 Stacks:-

package com.devinline.stacks;

/*Queue implementation assuming pop operation is costly*/
public class CustomQueueUsingTwoStack {
StackCustom s1 = null;
StackCustom s2 = null;

public CustomQueueUsingTwoStack() {
s1 = new StackCustom();
s2 = new StackCustom();
}

/* Internally call push operation of order O(1) */
void enQueue(int data) {
s1.push(data);
}

/* Internally call pop operation of amortized complexity order O(1) */
int deQueue() {
int temp = -999999; // A marker value indicating empty queue
/* If S2 is not empty, return top element in O(1) */
if (!s2.isEmplty()) {
return s2.pop();
}
if (s1.isEmplty()) {
System.out.println("Queue is empty!!");
}
while (!s1.isEmplty()) {
temp = s1.peek();
s2.push(s1.pop());
}
/* Remove top element from S2 */
if (!s2.isEmplty())
s2.pop();
return temp;
}

boolean isEmptyQueue() {
return true;
}

int getQueueSize() {
int size = 0;

if (!s1.isEmplty()) {
size += s1.getSize();
}
if (!s2.isEmplty()) {
size += s2.getSize();
}
return size;
}

public String toString() {
StringBuffer str = new StringBuffer();
if (!s1.isEmplty()) {
str.append(s1.toString());
}
if (!s2.isEmplty()) {
str.append(s2.toString());
}
return str.toString();
}

}

class SinglyLinkedList {
Node head = null;

private void createLikedList() {
head = null;
}

public static Node createNewNode(int data) {
return new Node(data);
}

/* get first element */
public Node getFistNode() {
if (head == null)
return null;
else
return head;
}

/* Delete First node,return new head */
public Node deleteFirstNode() {
if (head == null)
return null;
Node temp = head.next;
Node delNode = head;
head.next = null;// garbage collected
head = temp;
return delNode;
}

/* Display data of nodes/iterate linked list */
public String iterateLinkedList() {
StringBuffer sbf = new StringBuffer();
Node current = head;
if (head != null) {
sbf.append("[");
while (current != null) {
sbf.append(current.data + " ");
current = current.next;
}
sbf.append(" ]");
} else {
System.out.println("Linked list is empty.");
}
return sbf.toString();

}

/* Add New node at start of linked list */
public void insertFirst(int data) {
Node newNode = createNewNode(data);
if (head == null) {
head = newNode;
} else {
newNode.next = head;
head = newNode;
}
}

}

class Node {
public int data;
public Node next;

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

class StackCustom {
Node node = null;
int top = -1;
SinglyLinkedList list;

public StackCustom() {
createStack();
}

void createStack() {
top = -1;
list = new SinglyLinkedList();
}

int pop() {
if (list.getFistNode() != null) {
top--;
return list.deleteFirstNode().data;
} else
return -1;
}

void push(int data) {
list.insertFirst(data);
++top;
}

int peek() {
return list.getFistNode().data;
}

boolean isEmplty() {
return (top == -1) ? true : false;
}

public String toString() {
return list.iterateLinkedList();
}

public int getSize() {
return top + 1;
}
}

Test client program:-

package com.devinline.stacks;

public class customQueueTestClient {

public static void main(String[] args) {
CustomQueueUsingTwoStack queue = new CustomQueueUsingTwoStack();
queue.enQueue(12);
queue.enQueue(52);
queue.enQueue(62);
queue.enQueue(162);
queue.enQueue(222);
System.out.println("Five enQueue operation" + queue.toString());
System.out.println("Queuue size is: " + queue.s1.getSize());
System.out.println("deQueue() operation - deQueued element: "
+ queue.deQueue());
System.out.println("deQueue() operation- deQueued element: "
+ queue.deQueue());
System.out.println("Queuue size is: " + queue.getQueueSize());

queue.enQueue(62);
queue.enQueue(162);
System.out.println("Two enQueue operation: " + queue.toString());
System.out.println("Intermediate size after enQueue(s1 + s2): "
+ queue.getQueueSize());
System.out.println("deQueue() - deQueued element: " + queue.deQueue());
System.out.println("deQueue() - deQueued element: " + queue.deQueue());
System.out.println("deQueue() - deQueued element: " + queue.deQueue());
System.out.println("deQueue() - deQueued element: "
+ queue.getQueueSize());
System.out.println("deQueue() - deQueued element: " + queue.deQueue());
System.out.println("Queuue size is: " + queue.getQueueSize());
queue.enQueue(76);
queue.enQueue(453);
queue.enQueue(122);
queue.enQueue(192);
queue.enQueue(82);
System.out.println("Five enQueue operation: " + queue.toString());
System.out.println(queue.getQueueSize());
System.out.println("deQueue() - deQueued element: " + queue.deQueue());
System.out.println(queue.getQueueSize());
}

}
==========Sample output=============
Five enQueue operation[222 162 62 52 12  ]
Queuue size is: 5
deQueue() operation - deQueued element: 12
deQueue() operation- deQueued element: 52
Queuue size is: 3
Two enQueue operation: [162 62  ][62 162 222  ]
Intermediate size after enQueue(s1 + s2): 5
deQueue() - deQueued element: 62
deQueue() - deQueued element: 162
deQueue() - deQueued element: 222
deQueue() - deQueued element: 2
deQueue() - deQueued element: 62
Queuue size is: 1
Five enQueue operation: [82 192 122 453 76  ][162  ]
6
deQueue() - deQueued element: 162
5
====================================

Note:- We have made push() operation less costlier as compare to pop() , we can reverse this implementation and cane make push() operation  costlier.

Apr 16, 2014

Textual description of firstImageUrl

Internal implementation of collections in java - Internal workings of HashMap, HashSet, etc.

It is most common interview question for senior and mid senior level java developer, specially in product company to check in depth understanding of "Internal implementations of various collections like HashMap, HashSet, LinkedHashMap, etc". Here I have documented for some of them and will add many more. Hope it will be good reading for and helpful before going for an interview.
Every Java developer more or less witness use of HashMap in software development process and quite familiar with the put/get operations associated with HashMap. However, how does HashMap works internally is not known by many people unless they make effort to see source code of java.util.HashMap class (JDK). Do you know HashMap internally uses an associative array data structure for storing key/Value pair ? It's very right time to learn internal working of HashMap and understand the underlying internal class structure, implementation and its workingClick here to find detailed explanation.


HashSet is the very obvious choice among developer when they want to store unique objects (Duplicates not allowed). Do you know HashSet uses HashMap internally to store unique objects?.If your answer is NO, then it is very right time to understand how HashSet maintain uniqueness using HahMap and makes our life easy. Here we have an detail discussion to learn and understand internal class structure, implementation and its internal working. Click here to find tutorial with detailed explanation.

HashMap does not maintain order of element and does not give any guarantee of retrieval in same sequence as they were inserted.When we need to maintain order of elements either insertion or access order then LinkedHashMap come for our rescue. What is special about LinkedHashmap which helps maintain order of element. Its is the LinkedList which LinkedHashMap maintain internally to keep control over order of elements inserted.
Click here to find detail discussion of internal class structure, implementation and its working.

====================== End of article ===========================
Happy Learning!!
Nikhil
     

Apr 15, 2014

Textual description of firstImageUrl

How LinkedHashMap works internally - Internal implementation of LinkedHashMap

LinkedHashMap is one of the concrete implementation of Map (an associative array data structure).The main agenda of this post is to discuss internal structure of class LinkedHashMap and its internal working.Before going into delve of internal working of LinkedHashMap one should understand internal working of HashMap which  is discussed here.
In layman terminology LinkedHashmap is combination of both LinkedList and HashMap.In other words, LiknedHashMap maintain a linkedList of elements in order of being inserted or being accessed along with storing elements(key and value) in HashMap.
Internal building blocks of LinkedHashMap is similar to HashMap with extra overhead for maintaining a linkedList(or interconnecting all elements in a perticular order). LinkedHashMap uses an array of Entry objects (Entry[] table) to store elements and maintain two referenes(Entry<K,V> before, after;) to form a doubly linkedList. Please note HashMap also uses Entry objects to store key/value then what makes LinkedHashMap Entry class different.We will walk through the sample code from java.util.LinkedHashMap to find differences:
 static class Entry extends HashMap.Entry{
  Entry before, after;  
  Entry(int hash, K key, V value, HashMap.Entry next){
   super(hash,key,value,next);
  }
 }
As we can see the visible difference, above Entry class extends HashMap Entry class and add two references for interconnecting elements to be added in map via put method. super(hash,key,value,next) is used to instantiate HashMap entry objects. HashMap Entry object looks like this :
 static class Entry{
        final K key;
        V value;
        Entry next;
        final int hash;
  } 
We have now fair idea how Entry object is created and stored in Entry[] table.Now question arises how does linkedList is maintained using before and after references ?
For maintaining a doubly linkedList, LinkedHashMap uses a reference head of Entry type and initializes it before any entries are inserted into the map.
  private transient Entry header;
  //Called by superclass constructors and pseudoconstructors before
 //any entries are inserted into the map.Initializes the chain.
 void init() {
        header = new Entry(-1, null, null, null);
        header.before = header.after = header;
  }
When we do put operation, call is redirected to a method called addEntry and it add elemets at end of the linkedlist and maintains references before/after.Similarly, on remove of an element referenes are reset and pointed to correct Entry object.
One important point that need special mention is that, by default LinkedHashMap maintains linkedList in insertion order or Linkedlist is iterated in same order how elements were inserted. However, it can be changed by using appropriate constructor. The iteration ordering is controlled by accessOrder(a boolean field maintained by LinkedHashMap).
for access-order    ----> accessOrder = true
for insertion-order-----> accessOrder =false
We have two constructor below: first constructor is default one and it supports insertion order. However second constructor uses a argument value for setting accessOrder.(Same shown below)
  private final boolean accessOrder;
 //First default constructor 
 public LinkedHashMap(){
             super();
             accessOrder = false;
        }
 //second constructor :
 public LinkedHashMap(int initialCapacity,
   float loadFactor, boolean accessOrder) {
 super(initialCapacity, loadFactor);
 this.accessOrder = accessOrder;
}
Consider we have created a LinkedHashMap by using default constructor and inserted 4 elements[(1,"Nikhil"),(2,"ranjan"),(3,"Oracle"),(4,"java")]. Following diagram depicts how it will be stored internally :(Assuming index is calculated and it comes out as 5 for key 1, 9 for key 2, and so on)
Graphical depiction of how elements are stored in array and linkedlist

When first element <1,"Nikhil"> is inserted, it is stored in index position 5 and  head's after start pointing to Nikhil and Nikhil before pointing to head. After that when <2, "Ranjan">  is added  Nikhil's after pointing to Ranjan. similarly all elements are added and  before/after is updated accordingly.
This is all about LinkedHashMap and it's detailed code can be found here.
======================End of article==========================

References :
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b27/java/util/LinkedHashMap.java

Apr 13, 2014

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  ]
===================================