Given two sorted linked lists, merge these two lists to create one single sorted linked list.

Your method will be passed two parameters - pointers to the head of the two sorted linked.

Your method must return pointer to the head of the linked list. Do not create any new node in your solution. Only adjust the links in the nodes.

Here we are given Heads of two sorted Linked Lists and we have to merge them and return the head of the newly created sorted linked list.

We will use recursion to solve this problem. Compare the head of two linked lists. We can have below cases:

• Both are NULL - return NULL. if(A == NULL && B == NULL) return NULL;
• One of them is NULL - return the NOT-NULL node else if (A == NULL && B!= NULL) return B; else if (B == NULL && A != NULL) return A;
• head of A is lesser in value - In this case, we can pick the head of A as head of the merged list. We can break the problem into sub-problem. Merge the sub-list of A after excluding the head with complete B. And set the returned head of the merge as next of A. and now return A because its the head. A->next = MergeLists(A->next,B); return A;
• head of B is lesser or equal in value - Here, we can pick the head of B as head of the merged list. We can break the problem as merge the sublist of B after excluding head with complete A. B->next = MergeLists(A,B->next); return B;

editorial written by ishabh

/*
  Merge two sorted lists A and B as one linked list
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
Node* MergeLists(Node *A,Node* B)
{
  // BASE cases for recursion
  if(A == NULL && B == NULL) return NULL;
  else if (A == NULL && B!= NULL) return B;
  else if (B == NULL && A != NULL) return A;
  // If data in A is lesser, pick the head of A and solve subproblem
  // of merging remaining part of A with B using recursion. Set the return as next of 
  // as next of the picked node i.e head of A. 
  else if(A->data < B->data) 
  {
     A->next = MergeLists(A->next,B);
     return A;
  }
  // If data in B is lesser or equal, pick the head of B and solve subproblem
  // of merging remaining part of B with A using recursion. Set the return as next of 
  // as next of the picked node i.e head of B. 
  else
  {
    cod
  }
}

featured solution by ishabh