class Node {
Node next;
int value;
Node(int val) {
this.value = val;
this.next = null;
}
@Override
Node cur = this;
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);
}
} else if(n1!=null ){
result=n1;
} else if(n2!=null){
result=n2;
}
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
)); }
}
Y2xhc3MgTm9kZSB7CgoJTm9kZSBuZXh0OwoJaW50IHZhbHVlOwoJCglOb2RlKGludCB2YWwpIHsKCQl0aGlzLnZhbHVlID0gdmFsOwoJCXRoaXMubmV4dCA9IG51bGw7Cgl9CgkKCUBPdmVycmlkZQoJcHVibGljIFN0cmluZyB0b1N0cmluZygpIHsKCQlOb2RlIGN1ciA9IHRoaXM7CgkJU3RyaW5nIHN0ciA9ICIiOwoJCQoJCXdoaWxlKGN1ciAhPSBudWxsKSB7CgkJCXN0ciArPSBjdXIudmFsdWUrIi0+IjsKCQkJY3VyID0gY3VyLm5leHQ7CgkJfQoJCQoJCXJldHVybiBzdHI7Cgl9Cn0KCmNsYXNzIE1lcmdlTEwgewoKCXB1YmxpYyBzdGF0aWMgTm9kZSBtZXJnZShOb2RlIG4xLCBOb2RlIG4yKSB7CgkJCiAgICAgICAgTm9kZSByZXN1bHQgPSBudWxsOwogICAgICAgIAogICAgICAgIGlmKG4xICE9IG51bGwgJiYgbjIgIT0gbnVsbCkgewogICAgICAgICAgICBpZihuMS52YWx1ZSA8IG4yLnZhbHVlKSB7CiAgICAgICAgICAgIAlyZXN1bHQgPSBuMTsKICAgICAgICAgICAgCXJlc3VsdC5uZXh0ID0gbWVyZ2UobjEubmV4dCwgbjIpOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAJcmVzdWx0ID0gbjI7CiAgICAgICAgICAgIAlyZXN1bHQubmV4dCA9IG1lcmdlKG4xLCBuMi5uZXh0KTsKICAgICAgICAgICAgfQogICAgICAgIH0gZWxzZSBpZihuMSE9bnVsbCApewogICAgICAgICAgICByZXN1bHQ9bjE7CiAgICAgICAgfSBlbHNlIGlmKG4yIT1udWxsKXsKICAgICAgICAgICAgcmVzdWx0PW4yOwogICAgICAgIH0KCQlyZXR1cm4gcmVzdWx0OwoJfQoJCglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CgkJTm9kZSBuMSA9IG5ldyBOb2RlKDEpOwoJCU5vZGUgbjMgPSBuZXcgTm9kZSgzKTsKCQlOb2RlIG41ID0gbmV3IE5vZGUoNSk7CgkJTm9kZSBuNyA9IG5ldyBOb2RlKDcpOwoJCU5vZGUgbjkgPSBuZXcgTm9kZSg5KTsKCQkKCQluMS5uZXh0ID0gbjM7CgkJbjMubmV4dCA9IG41OwoJCW41Lm5leHQgPSBuNzsKCQluNy5uZXh0ID0gbjk7CgkJbjkubmV4dCA9IG51bGw7CgkJCgkJTm9kZSBuMiA9IG5ldyBOb2RlKDIpOwoJCU5vZGUgbjQgPSBuZXcgTm9kZSg0KTsKCQlOb2RlIG42ID0gbmV3IE5vZGUoNik7CgkJTm9kZSBuOCA9IG5ldyBOb2RlKDgpOwoJCU5vZGUgbjEwID0gbmV3IE5vZGUoMTApOwoJCQoJCW4yLm5leHQgPSBuNDsKCQluNC5uZXh0ID0gbjY7CgkJbjYubmV4dCA9IG44OwoJCW44Lm5leHQgPSBuMTA7CgkJbjEwLm5leHQgPSBudWxsOwoJCQoJCVN5c3RlbS5vdXQucHJpbnRsbigiTWVyZ2UgOiAiICsgbWVyZ2UobjEsIG4yKSk7Cgl9Cn0K