21. Merge Two Sorted Lists

1. 问题描述

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.
Tags：Linked List
Similar Problems： (H) Merge k Sorted Lists (E) Merge Sorted Array (M) Sort List (M) Shortest Word Distance II

2. 解答思路

3. 代码

 1 struct ListNode {
 2     int val;
 3     ListNode *next;
 4     ListNode(int x) : val(x), next(NULL) {}
 5 };
 6 class Solution {
 7 public:
 8     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
 9         if (NULL == l1)
10         {
11             return l2;
12         }
13         else if (NULL == l2)
14         {
15             return l1;
16         }
17         ListNode *pHead = NULL;
18         ListNode *pt = NULL;
19         while (NULL != l1 && NULL != l2)
20         {
21             if (l1->val > l2->val)
22             {
23                 if (pt == NULL)
24                 {
25                     pt = l2;
26                 }
27                 else
28                 {
29                     pt->next = l2;
30                     pt = l2;                    
31                 }                
32                 l2 = l2->next;
33                 pt->next = NULL;
34                 if(NULL == pHead)
35                 {
36                     pHead = pt;
37                 }
38             }
39             else
40             {
41                 if (pt == NULL)
42                 {
43                     pt = l1;
44                 }
45                 else
46                 {
47                     pt->next = l1;
48                     pt = l1;
49                     
50                 }                
51                 l1 = l1->next;
52                 pt->next = NULL;
53                 if(NULL == pHead)
54                 {
55                     pHead = pt;
56                 }
57                 else
58                 {
59 
60                 }
61             }        
62         }
63         if (NULL != l1)
64         {
65             while(NULL != l1)
66             {
67                 pt->next = l1;
68                 pt = l1;
69                 l1 = l1->next;
70                 pt->next = NULL;                
71             }            
72         }
73         else
74         {
75             while(NULL != l2)
76             {
77                 pt->next = l2;
78                 pt = l2;
79                 l2 = l2->next;
80                 pt->next = NULL;
81             }
82         }
83         return pHead;
84     }
85 };

4. 反思

更优的解法：

 1 ListNode* mergeTwoLists_Better(ListNode* l1, ListNode* l2)
 2     {
 3         ListNode *helper = new ListNode(0);
 4         ListNode *head = helper;
 5         while(l1 && l2)
 6         {
 7             if(l1->val < l2->val)
 8             {
 9                 helper->next = l1;
10                 l1 = l1->next;
11             }
12             else
13             {
14                 helper->next = l2;
15                 l2 = l2->next;
16             }
17             helper = helper->next;
18         }
19         if(l1)
20         {
21             helper->next = l1;
22         }
23 
24         if(l2) 
25         {
26             helper->next = l2;
27         }
28         return head->next;
29     }