leetcode题解 21.合并两个有序链表

题目

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

来源:力扣(LeetCode)

题解

这道题速度快和内存少,基本上就是迭代更新节点的方法,这样用去的时间是O(min(len(l1), len(l2))),使用的空间就只有一两个指针,也就是S(1)。如果使用一个新的链表去承接这些节点,那么空间复杂度就有O(n)了。

这个题解中最精髓的地方在循环判断的l1 && l2和之后循环结束的o->next = l1?l1:l2;

因为输入的链表是有序的,所以在将其中一个链表扫描完成之后,只需要将另一条链表直接连接在末尾就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *o, begin(0);
o = &begin;
while (l1 && l2) {
if (l1->val <= l2->val) {
o->next = l1;
l1 = l1->next;
} else {
o->next = l2;
l2 = l2->next;
}
o = o->next;
}
o->next = l1?l1:l2;
return begin.next;
}
};

结果

执行用时 : 12 ms, 在所有 C++ 提交中击败了86.67%的用户
内存消耗 : 8.7 MB, 在所有 C++ 提交中击败了95.20%的用户

Author: SmallXeon
Link: https://hexo.chensmallx.top/2019/07/29/leetcode-21-mergeTwoLists/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
一些推广链接
几个便宜量大的小✈场: FASTLINK, YToo, 论坛邀请注册: ,
便宜量大但是稳定性不足的VPS: , 价格略贵但好用的VPN: , ,