leetcode: 合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
还是一道简单题，是对于两个已经有序了的链表的合并操作，思路就是不断取两个链表的链头进行比较，取小的值作为新链表的尾结点值，两个链表遍历到都为空时两个链表就合并为新链表了
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
27
28
29
30
31
32
33
34
| class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
lhead = ListNode(0)
lpre = lhead
while l1 and l2:
if l1.val <= l2.val:
a = ListNode(l1.val);
lpre.next = a;
l1 = l1.next;
lpre = lpre.next;
else:
a = ListNode(l2.val);
lpre.next = a;
l2 = l2.next;
lpre = lpre.next;
while l1 != None:
a = ListNode(l1.val);
lpre.next = a;
l1 = l1.next;
lpre = lpre.next;
while l2 != None:
a = ListNode(l2.val);
lpre.next = a;
l2 = l2.next;
lpre = lpre.next;
return lhead.next;
|
可以发现在时间和内存上都是有问题，能通过测试但是可以做一些优化，直接用提供的链表结点，这样就省下了建立结点的空间与时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
lhead = ListNode(0)
lpre = lhead
while l1 and l2:
if l1.val <= l2.val:
lpre.next = l1;
l1 = l1.next;
else:
lpre.next = l2;
l2 = l2.next;
lpre = lpre.next;
if l1 != None:
lpre.next = l1;
else:
lpre.next = l2;
|
除了上面的解法，官方的解法还有一个直接调用函数的（python不仅包多，稀奇古怪的函数也多啊= =）
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def mergeTwoLists(self, l1, l2):
if l1 is None:
return l2
elif l2 is None:
return l1
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
|
今天看漫画的鬼才汉化组
打啵教程：
仪容仪表很重要
前提你得有女票
by全员已婚的飞橙汉化组
我酸了: - (