Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

C++:
01 void enList(ListNode*& head, ListNode*& tail, ListNode* p)
02 {
03     if(p==NULL)
04         return;
05     if(head==NULL){
06         head=tail=p;
07     }else{
08         tail->next=p;
09         tail=p;
10     }
11 }
12 
13 ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
14 {
15     if(l1==NULL)
16         return l2;
17     if(l2==NULL)
18         return l1;
19     ListNode* a=l1;
20     ListNode* b=l2;
21     ListNode* head=NULL;
22     ListNode* tail=NULL;
23     while(a&&b){
24         if(a->val<=b->val){
25             enList(head,tail,a);
26             a=a->next;
27         }else{
28             enList(head,tail,b);
29             b=b->next;
30         }
31     }
32     if(a){
33         tail->next=a;
34     }else{
35         tail->next=b;
36     }
37     return head;
38 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s