Given two sorted linked lists, merge these two lists to create one single sorted linked list.
InputYour method will be passed two parameters - pointers to the head of the two sorted linked.
OutputYour 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:
if(A == NULL && B == NULL) return NULL;
else if (A == NULL && B!= NULL) return B;
else if (B == NULL && A != NULL) return A;
A->next = MergeLists(A->next,B);
return 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