#include <stdio.h>
#include <stdlib.h>
struct listNode{
int data;
struct listNode* next;
} typedef listNode;
/* Function to print nodes in a given linked list */
void printList(listNode *node){
while(node != NULL){
node = node->next;
}
}
void push(listNode **head, int data){
listNode
*temp
= (listNode
*)malloc(sizeof(listNode
)); temp->data = data;
temp->next = *head;
*head = temp;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct listNode* mergeTwoLists(struct listNode* a, struct listNode* b) {
struct listNode* result = NULL;
/* Base cases */
if (a == NULL)
return(b);
else if (b == NULL)
return(a);
/* Pick either a or b, and recur */
if (a->data <= b->data) {
result = a;
result->next = mergeTwoLists(a->next, b);
}else {
result = b;
result->next = mergeTwoLists(a, b->next);
}
return(result);
}
/* Driver program to test above functions*/
int main(){
/* Start with the empty list */
listNode *a = NULL;
listNode *b = NULL;
/* Let us create a unsorted linked lists to test the functions
Created lists shall be a: 2->3->20->5->10->15 */
push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&b, 20);
push(&b, 3);
push(&b, 2);
push(&b, 1);
printList(a);
printList(b);
/* Sort the above created Linked List */
listNode *result = mergeTwoLists(a, b);
printf("Merged Linked List is: "); printList(result);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCnN0cnVjdCBsaXN0Tm9kZXsKCWludCBkYXRhOwoJc3RydWN0IGxpc3ROb2RlKiBuZXh0Owp9IHR5cGVkZWYgbGlzdE5vZGU7CgovKiBGdW5jdGlvbiB0byBwcmludCBub2RlcyBpbiBhIGdpdmVuIGxpbmtlZCBsaXN0ICovCnZvaWQgcHJpbnRMaXN0KGxpc3ROb2RlICpub2RlKXsKICB3aGlsZShub2RlICE9IE5VTEwpewogIAlwcmludGYoIiVkICIsIG5vZGUtPmRhdGEpOwogICAJbm9kZSA9IG5vZGUtPm5leHQ7CiAgfQogIHByaW50ZigiXG4iKTsKfQoKdm9pZCBwdXNoKGxpc3ROb2RlICoqaGVhZCwgaW50IGRhdGEpewoJbGlzdE5vZGUgKnRlbXAgPSAobGlzdE5vZGUgKiltYWxsb2Moc2l6ZW9mKGxpc3ROb2RlKSk7Cgl0ZW1wLT5kYXRhID0gZGF0YTsKCXRlbXAtPm5leHQgPSAqaGVhZDsKCSpoZWFkID0gdGVtcDsKfQoKLyoqCiAqIERlZmluaXRpb24gZm9yIHNpbmdseS1saW5rZWQgbGlzdC4KICogc3RydWN0IExpc3ROb2RlIHsKICogICAgIGludCB2YWw7CiAqICAgICBzdHJ1Y3QgTGlzdE5vZGUgKm5leHQ7CiAqIH07CiAqLwpzdHJ1Y3QgbGlzdE5vZGUqIG1lcmdlVHdvTGlzdHMoc3RydWN0IGxpc3ROb2RlKiBhLCBzdHJ1Y3QgbGlzdE5vZGUqIGIpIHsKICAgIHN0cnVjdCBsaXN0Tm9kZSogcmVzdWx0ID0gTlVMTDsgIAogICAvKiBCYXNlIGNhc2VzICovICAKICAgaWYgKGEgPT0gTlVMTCkgIAogICAgIHJldHVybihiKTsgIAogICBlbHNlIGlmIChiID09IE5VTEwpICAKICAgICByZXR1cm4oYSk7ICAKICAgLyogUGljayBlaXRoZXIgYSBvciBiLCBhbmQgcmVjdXIgKi8gIAogICBpZiAoYS0+ZGF0YSA8PSBiLT5kYXRhKSB7ICAKICAgICByZXN1bHQgPSBhOyAgCiAgICAgcmVzdWx0LT5uZXh0ID0gbWVyZ2VUd29MaXN0cyhhLT5uZXh0LCBiKTsgIAogICB9ZWxzZSB7ICAKICAgICByZXN1bHQgPSBiOyAgCiAgICAgcmVzdWx0LT5uZXh0ID0gbWVyZ2VUd29MaXN0cyhhLCBiLT5uZXh0KTsgIAogICB9ICAKICAgcmV0dXJuKHJlc3VsdCk7IAp9CgovKiBEcml2ZXIgcHJvZ3JhbSB0byB0ZXN0IGFib3ZlIGZ1bmN0aW9ucyovCmludCBtYWluKCl7CiAgLyogU3RhcnQgd2l0aCB0aGUgZW1wdHkgbGlzdCAqLwogIGxpc3ROb2RlICphID0gTlVMTDsKICBsaXN0Tm9kZSAqYiA9IE5VTEw7CiAgCiAgLyogTGV0IHVzIGNyZWF0ZSBhIHVuc29ydGVkIGxpbmtlZCBsaXN0cyB0byB0ZXN0IHRoZSBmdW5jdGlvbnMKICBDcmVhdGVkIGxpc3RzIHNoYWxsIGJlIGE6IDItPjMtPjIwLT41LT4xMC0+MTUgKi8KICBwdXNoKCZhLCAxNSk7CiAgcHVzaCgmYSwgMTApOwogIHB1c2goJmEsIDUpOyAKCiAgcHVzaCgmYiwgMjApOwogIHB1c2goJmIsIDMpOwogIHB1c2goJmIsIDIpOyAKICBwdXNoKCZiLCAxKTsgCgogIHByaW50TGlzdChhKTsKICBwcmludExpc3QoYik7ICAgICAgICAgICAKICAvKiBTb3J0IHRoZSBhYm92ZSBjcmVhdGVkIExpbmtlZCBMaXN0ICovCiAgbGlzdE5vZGUgKnJlc3VsdCA9IG1lcmdlVHdvTGlzdHMoYSwgYik7CiAgcHJpbnRmKCJNZXJnZWQgTGlua2VkIExpc3QgaXM6ICIpOwogIHByaW50TGlzdChyZXN1bHQpOyAgICAgICAgICAgCiAgCiAgcmV0dXJuIDA7Cn0=