Problem:Given two linked lists sorted in increasing order. Merge them both in such a way that the result list is in decreasing order. Both the Linked list can be of different sizes.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
/* The structure of linked list is the following struct Node { int data; Node* next; }; */ struct Node * mergeResult(Node *node1,Node *node2) { // your code goes here Node *head,*tmp,*tmp2; Node *p; bool f=0; int a,b; tmp=node1; tmp2=node2; while(tmp!=NULL && tmp2!=NULL) { a=tmp->data; b=tmp2->data; if(a<b) { tmp=tmp->next; if(f==0) { head=new Node; head->data=a; head->next=NULL; f=1; } else { p=new Node; p->data=a; p->next=head; head=p; } } else if(a>b) { tmp2=tmp2->next; if(f==0) { head=new Node; head->data=b; head->next=NULL; f=1; } else { p=new Node; p->data=b; p->next=head; head=p; } } else if(a==b) { tmp=tmp->next; tmp2=tmp2->next; if(f==0) { head=new Node; head->data=b; p=new Node; p->data=b; p->next=NULL; head->next=p; f=1; } else { p=new Node; p->data=a; p->next=head; head=p; p=new Node; p->data=b; p->next=head; head=p; } } } while(tmp!=NULL) { a=tmp->data; p=new Node; p->data=a; p->next=head; head=p; tmp=tmp->next; } while(tmp2!=NULL) { a=tmp2->data; p=new Node; p->data=a; p->next=head; head=p; tmp2=tmp2->next; } return head; } |