Thread: Merge two sorted Linked Lists

Write a program to merge two sorted linked lists. Consider all possible test cases.

Structure definition:

Code:

typedef struct linkedList* List;
struct linkedList{
	int num;
	struct linkedList *next;
};

Code:

List mergeList(List L, List L1)
{
	List t1=NULL, t2=NULL, temp=NULL, root=NULL;
	
	if(!L && !L1) {
		cout<<"Both are NULL"<<endl;
		return NULL;
	}
	else if(!L)
		return L1;
	else if(!L1) {
		cout <<"Second is NULL"<<endl;
		return L;
	}
	else {
		root = (L->num < L1->num)?L:L1;
		while(L && L1) {
			if(L->num < L1->num){
				while(L && (L->num <= L1->num)){
					t1 = L;
					L= L->next;
				}
				t1->next = L1;
			}
			else if(L->num > L1->num){
				while(L1 && (L->num > L1->num)){
					t2 = L1;
					L1 = L1->next;
				}
				t2->next = L;
			}
			else {
				t1 = L;
				temp = L->next;
				L->next = L1;
				L = temp;
			}
		}
		return root;
	}
	
}