[LeetCode] 021. Merge Two Sorted Lists (Easy) (C++/Python)

索引：[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. 开一个节点做 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;elsecur->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 ListNodedef mergeTwoLists(self, l1, l2):if not l1 and not l2:return Nonedummy = ListNode(0)cur = dummywhile l1 and l2:if l1.val <= l2.val:cur.next = l1l1 = l1.nextelse:cur.next = l2l2 = l2.nextcur = cur.nextcur.next = l1 or l2return dummy.next

爱情纯属天性，不用思考。你不能为爱而爱，