CareerCup

private static LinkedList merge(Node a, Node b) {
		// TODO Auto-generated method stub
		LinkedList merge = new LinkedList();
		Node dummy=new Node();
		Node tail = dummy;
		while(a!=null && b!=null){
			if(a.data<b.data){
				tail.next = a;
				a= a.next;
				tail = tail.next;
			}
			else{
				tail.next = b;
				b=b.next;
				tail = tail.next;
			}
		}
		if(a==null){
			tail.next = b;
		}
		if(b==null){
			tail.next =a;
		}
		merge.root = dummy.next;
		return merge;
	}

How about this

//Make sure list1.data < list2.data
public Node mergeLinkedList(Node list1, Node list2){

	if(list1 == null) return list2;
	if(list2 == null) return list1;

	while(list1.next != null && list2.next !=null){
		if(list1.data <= list2.data) list1 = list1.next;
	}

	list1.next = mergeLinkedList(list2, list1);
	return list1;
}

NA