21. 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.

**Example:**

1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
思路:链表的使用,是我的薄弱项~本题的思路是逐个比较,较小的数插入到链表中。可以新建链表,也可以在已有的链表中插入,节省空间,但会破坏源数据。因为新链表不会占用太多空间,选择新建链表。代码如下。**这道题需要重点关注,涉及到链表的一些操作。**网上写法也非常多,参考下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(-1), *cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return dummy->next;
}
};
Res. Runtimes: 4ms, Ranking 100.00% 网上其他解法(递归):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
更简洁的写法,去掉if从句:
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
ListNode *head = l1->val < l2->val ? l1 : l2;
ListNode *nonhead = l1->val < l2->val ? l2 : l1;
head->next = mergeTwoLists(head->next, nonhead);
return head;
}
};
丧心病狂的解法,三行搞定!
1
2
3
4
5
6
7
8
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1 || (l2 && l1->val > l2->val)) swap(l1, l2);
if (l1) l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
};