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 /**
02  * Definition for singly-linked list.
03  * struct ListNode {
04  *     int val;
05  *     ListNode *next;
06  *     ListNode(int x) : val(x), next(NULL) {}
07  * };
08  */
09  void mergeTwoListHelper(ListNode*& head, ListNode*& end, ListNode* add)
10  {
11      if(head==NULL)
12      {
13          head=end=add;
14      }
15      else
16      {
17          end->next=add;
18          end=add;
19      }
20  }
21 
22 class Solution {
23 public:
24     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
25         // Start typing your C/C++ solution below
26         // DO NOT write int main() function
27         ListNode* hd=NULL;
28         ListNode* end=NULL;
29         while((l1!=NULL)||(l2!=NULL))
30         {
31             if(l2==NULL)
32             {
33                 mergeTwoListHelper(hd,end,l1);
34                 l1=l1->next;
35             }
36             else if(l1==NULL)
37             {
38                 mergeTwoListHelper(hd,end,l2);
39                 l2=l2->next;
40 
41             }
42             else if(l1->val>l2->val)
43             {
44                 mergeTwoListHelper(hd,end,l2);
45                 l2=l2->next;
46             }
47             else
48             {
49                 mergeTwoListHelper(hd,end,l1);
50                 l1=l1->next;
51             }
52         }
53         return hd;
54     }
55 };
Advertisements
This entry was posted in Array and linked list, Recursive. 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