【leetcode】Merge Two Sorted Lists

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.

每次找到两个链表中小的一个，把他连接在后面，直到连接完成

思路1：利用递归方法解：递归思路：

if(l1->val<=l2->val)

{

head=l1;

head->next=mergeTwoLists(l1->next,l2);

}

else

{

head=l2;

head->next=mergeTwoLists(l1,l2->next);

}

 1 class Solution {
 2 public:
 3     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {                  
 4          
 5         if(l1==NULL)
 6         {
 7             return l2;
 8         }
 9        
10         if(l2==NULL)
11         {
12             return l1;
13         }
14        
15         ListNode *head;
16        
17         if(l1->val<=l2->val)
18         {
19             head=l1;
20             head->next=mergeTwoLists(l1->next,l2);
21         }
22         else
23         {
24             head=l2;
25             head->next=mergeTwoLists(l1,l2->next);
26         }
27        
28         return head;
29        
30     }
31 };

非递归解法：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
12        
13         if(l1==NULL)
14         {
15             return l2;
16         }
17        
18         if(l2==NULL)
19         {
20             return l1;
21         }
22        
23         ListNode *head=new ListNode(0);
24         ListNode *pre=head;
25        
26         while(l1!=NULL||l2!=NULL)
27         {
28             if(l1==NULL)
29             {
30                 head->next=l2;
31                 l2=l2->next;
32                 head=head->next;
33                 continue;
34             }
35            
36             if(l2==NULL)
37             {
38                 head->next=l1;
39                 l1=l1->next;
40                 head=head->next;
41                 continue;
42             }
43            
44             if(l1->val<=l2->val)
45             {
46                 head->next=l1;
47                 l1=l1->next;
48                 head=head->next;
49             }
50             else
51             {
52                 head->next=l2;
53                 l2=l2->next;
54                 head=head->next;
55             }
56         }
57        
58         ListNode *ret=pre->next;
59         delete pre;
60         return pre->next;
61        
62     }
63 };