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.

***Note***

Why would it will cause ERROR when not deleting line 15~17 or changing line 12 to

ListNode *pre_head = null; or ListNode *pre_head;

You have to notice the definition of ListNode. When you understand that you can not create an object withour giving an argument, you won't make mistakes.

Actually, you don't need to delete line 15~17, just correct line 15 and you will even save time. After editing, the run time is 15ms while before is 16ms.

Newly version. Runtime: 8ms

 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         if(!l1 && !l2) return l1;
13         if(!l1) return l2;
14         if(!l2) return l1;
15         
16         ListNode* pre = new ListNode(0);
17         ListNode* move = pre;
18         while(l1 && l2){
19             ListNode* temp = new ListNode(0);
20             if(l1->val < l2->val){
21                 temp->val = l1->val;
22                 l1 = l1->next;
23             }
24             else{
25                 temp->val = l2->val;
26                 l2 = l2->next;
27             }
28             move->next = temp;
29             move = move->next;
30         }
31         if(l1)
32             move->next = l1;
33         if(l2)
34             move->next = l2;
35             
36         return pre->next;
37     }
38 };

NEWLY VERSION!!!

Runtime: 8ms

 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         ListNode pre(-1);
13         
14         for(ListNode* p = &pre; l1 || l2; p = p->next){
15             int val1 = l1 == nullptr ? INT_MAX : l1->val;
16             int val2 = l2 == nullptr ? INT_MAX : l2->val;
17             
18             if(val1 > val2){
19                 p->next = l2;
20                 l2 = l2->next;
21             }
22             else{
23                 p->next = l1;
24                 l1 = l1->next;
25             }
26         }
27         return pre.next;
28     }
29 };

 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 //code below used 15ms on leetcode  platform
10 class Solution {
11 public:
12     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
13         if(!l1 && !l2) return NULL;
14         if(!l1) return l2;
15         if(!l2) return l1;
16         
17         ListNode *result = new ListNode(0);
18         ListNode *pre_head = result;
19         while(l1 && l2){
20             if(l1->val <= l2->val){
21                 result->next = l1;
22                 l1 = l1->next;
23             }
24             else{
25                 result->next = l2;
26                 l2 = l2->next;
27             }
28             result = result->next;
29         }
30         while(l1){
31             result->next = l1;
32             result = result->next;
33             l1 = l1->next;
34         }
35         while(l2){
36             result->next = l2;
37             result = result->next;
38             l2 = l2->next;
39         }
40         return pre_head->next;
41     }
42 };

View Code

 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         ListNode *pre_head = new ListNode(0);
13         ListNode *result = pre_head;
14         
15         //if(!l1 && !l2) return result;
16         //if(!l1 && l2) return l2;
17         //if(l1 && !l2) return l1;
18         
19         while(l1 || l2){
20             if(!l1){
21                 while(l2){
22                     result->next = l2;
23                     result = result->next;
24                     l2 = l2->next;
25                 }
26                 break;
27             }
28             else if(!l2){
29                 while(l1){
30                     result->next = l1;
31                     result = result->next;
32                     l1 = l1->next;
33                 }
34                 break;
35             }
36             else{
37                 if(l1->val <= l2->val){
38                     result->next = l1;
39                     l1 = l1->next;
40                 }
41                 else{
42                     result->next = l2;
43                     l2 = l2->next;
44                 }
45             }
46             result = result->next;
47             result->next = NULL;
48         }
49         return pre_head->next;
50     }
51 };