Merging two sorted linked list of unequal length
algorithm, data-structures, java, linked-list, mergesort
Solution
You need to add two more conditions, for when either `n1` or `n2` exhausts earlier. So, your condition - `n1 != null && n2 != null`, will only work in the case when both the list are of same size.
Just add code for below two conditions, after that if:
if(n1 != null && n2 != null) {
if(n1.value < n2.value) {
result = n1;
result.next = merge(n1.next, n2);
} else {
result = n2;
result.next = merge(n1, n2.next);
}
} else if (n1 != null) {
result = n1; // Add all the elements of `n1` to `result`
} else if (n2 != null) {
result = n2; // Add all the elements of `n2` to `result`
}
Actually, you don't need to build a new `result` list there. You can simply extend one of the passed Nodes.
You can modify your method as below:
public static Node merge(Node n1, Node n2) {
if (n1 == null) return n2;
if (n2 == null) return n1;
if (n1.value < n2.value) {
n1.next = merge(n1.next, n2);
return n1;
} else {
n2.next = merge(n2.next, n1);
return n2;
}
}
Problem
I was trying out the merging of two sorted linked list. The code snippet doesn't work for below two list : ``` List 1 : 1->3->5->7->9->null List 2 : 2->4->6->8->10->null Expected List : 1->2->3->4->5->6->7->8->9->10->null ``` But the output for below programs turns out to be this : ``` Output : 1->2->3->4->5->6->7->8->9->null // element 10 is missing. ``` Am I missing something ? Live Demo : http://ideone.com/O7MBlo ``` class Node { Node next; int value; Node(int val) { this.value = val; this.next = null; } @Override public String toString() { Node cur = this; String str = ""; while(cur != null) { str += cur.value+"->"; cur = cur.next; } return str; } } class MergeLL { public static Node merge(Node n1, Node n2) { Node result = null; if(n1 != null && n2 != null) { if(n1.value < n2.value) { result = n1; result.next = merge(n1.next, n2); } else { result = n2; result.next = merge(n1, n2.next); } } return result; } public static void main(String[] args) { Node n1 = new Node(1); Node n3 = new Node(3); Node n5 = new Node(5); Node n7 = new Node(7); Node n9 = new Node(9); n1.next = n3; n3.next = n5; n5.next = n7; n7.next = n9; n9.next = null; Node n2 = new Node(2); Node n4 = new Node(4); Node n6 = new Node(6); Node n8 = new Node(8); Node n10 = new Node(10); n2.next = n4; n4.next = n6; n6.next = n8; n8.next = n10; n10.next = null; System.out.println("Merge : " + merge(n1, n2)); } } ```