[LeetCode] 021. Merge Two Sorted Lists (Easy) (C++/Python)
來源：程序員人生 發布時間：2015-03-17 08:33:17 閱讀次數：3285次
索引：[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
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
