索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)
Github:
https://github.com/illuz/leetcode
021.Merge_Two_Sorted_Lists (Easy)
链接：
题目：https://oj.leetcode.com/problems/merge-two-sorted-lists/
代码(github)：https://github.com/illuz/leetcode
题意：
合并两个有序链表。
分析：
很经典的题目，不过知道怎样做后很容易，摹拟便可。
有两种做法：
1. 开1个节点做 head 的前节点 （下面的 Python 代码实现）
2. 不开直接做（C++ 代码实现）
代码：
C++:
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
if (l1 == NULL)
return l2;
if (l2 == NULL)
return l1;
ListNode *start, *cur;
if (l1->val < l2->val) {
cur = start = l1;
l1 = l1->next;
} else {
cur = start = l2;
l2 = l2->next;
}
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
cur->next = l1;
cur = l1;
l1 = l1->next;
} else {
cur->next = l2;
cur = l2;
l2 = l2->next;
}
}
if (l1 != NULL)
cur->next = l1;
else
cur->next = l2;
return start;
}
};
ListNode *l1, *l2, *ll1, *ll2;
int main() {
int n1, n2;
Solution s;
cin >> n1;
ll1 = l1 = new ListNode(0);
for (int i = 0; i < n1; i++) {
l1->next = new ListNode(0);
l1 = l1->next;
scanf("%d", &(l1->val));
}
cin >> n2;
ll2 = l2 = new ListNode(0);
for (int i = 0; i < n2; i++) {
l2->next = new ListNode(0);
l2 = l2->next;
scanf("%d", &(l2->val));
}
ListNode *res = s.mergeTwoLists(ll1->next, ll2->next);
while (res != NULL) {
cout << res->val << ' ';
res = res->next;
}
return 0;
}
Python:
class Solution:
# @param two ListNodes
# @return a ListNode
def mergeTwoLists(self, l1, l2):
if not l1 and not l2:
return None
dummy = ListNode(0)
cur = dummy
while l1 and 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 or l2
return dummy.next