Merge Sorted Linked Lists.

Given two sorted Linked Lists, we need to merge them into the third list in sorted order. Complexity – O(n)

Solution :

   public Node mergeList(Node a, Node b){
       Node result = null;
       if(a==null)
           return b;
       if(b==null)
           return a;

       if(a.data <= b.data){
           result =a;
           result.next = mergeList(a.next,b);
       }
       else
       {
           result =b;
           result.next = mergeList(b.next,a);
       }
       return result;
   }