题目一
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
- 大意:合并两个列表,返回一个新的列表,新的列表要把前边给定的两个列表链接起来。
思路:
其实就是把两个有序列表变成一个有序列表,只要维护两个指针,分别将当前最小的数复制到第三个列表中,然后将相应指针后移即可。道理很简单。
需要注意到是,python中,如果一个变量等于一个列表(比如,list1为一个列表,定义a1 = list1),则这个变量(a1)其实类似c中的指针的概念(a1和list1等价,都是“指针”),并不是拷贝了这个列表(如要实现拷贝复制,可以写a1 = list1[:])。
对于本题,这样的语法其实产生了两种写法,(见下边小节)。对于本题,两种写法都对,第一种写法比较简洁,但是却改变了原来的l1和l2列表,因为p3指针赋值的时候,直接用了l1或者l2的节点,那么下一次赋值的时候,便改变了这个节点的next指针。第二种写法采用了oj所定义的ListNode类的构造函数,直接用符合要求的l1或者l2的节点的val值创建一个新的node链接在l3后边,所以不改变原先的l1和l2列表。
所以,具体用哪一种,要根据知己需求定。
代码1(python)
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 |
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def mergeTwoLists(self, l1, l2): <!--more--> """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ p1 = l1 p2 = l2 l3 = ListNode(0) p3 = l3 while l1 and l2: if l1.val < l2.val: p3.next = l1 l1 = l1.next else: p3.next = l2 l2 = l2.next p3 = p3.next p3.next = l1 if not l2 else l2 return l3.next |
代码2(python)
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 35 36 37 38 39 40 41 |
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ p1 = l1 p2 = l2 l3 = ListNode(0) p3 = l3 while l1 and l2: if l1.val < l2.val: p3.next = ListNode(l1.val) p3 = p3.next l1 = l1.next else: p3.next = ListNode(l2.val) p3 = p3.next l2 = l2.next if not l1 and not l2: return l3.next elif not l1: while l2: p3.next = ListNode(l2.val) p3 = p3.next l2 = l2.next return l3.next else: while l1: p3.next = ListNode(l1.val) p3 = p3.next l1 = l1.next return l3.next |
题目二
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
- 大意:明显是前一道题的升级版,这次是合并k个已排序列表到一个列表。
思路0:
其实,这个就是一个归并排序,和归并排序不同的是,归并排序开始我们需要假设所有顺序都是乱的,我们假定每一个数都是一个list,然后逐步减少list数目,加长每一个list长度,而这道题,相当于已经进行到一半的归并排序。
不过,这没有关系,因为归并是递归实现的,我们玩全可以按照归并的方法,做这道题,而且正好用到了上一个题的代码。
代码:(Python)
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 35 36 37 38 39 40 |
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ if not lists: return None if len(lists) == 1: return lists[0] mid = len(lists) / 2 left = self.mergeKLists(lists[:mid]) right = self.mergeKLists(lists[mid:]) return self.merge2Lists(left, right) def merge2Lists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ l3 = ListNode(0) p3 = l3 while l1 and l2: if l1.val < l2.val: p3.next = l1 l1 = l1.next else: p3.next = l2 l2 = l2.next p3 = p3.next p3.next = l1 if not l2 else l2 return l3.next |
参考:
《百度百科 归并排序》( http://baike.baidu.com/link?url=V2OlIM61x3mTzbnICxp-CK5GD6CfSz1JHy4KWHLpcRbgd6LO8Nz9oYobdtF58Lat6-BfiB8F1NH2P49QW0vW9_ )
思路1:
用堆排序,用到了python的heapq这个数据结构。
代码(python):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ ret, heap = [], [] for li in lists: while li: heapq.heappush(heap, li.val) li = li.next while heap: ret.append(heapq.heappop(heap)) return ret |
思路2:
用python的排序,直接将所有列表的所有数放在一个列表中,然后直接用sorted()排序。
个人感觉:虽然投机取巧,但是速度一点也不慢,实际解决问题却最快速实用。
代码(Python):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ ret = [] for lst in lists: while lst: ret.append(lst.val) lst = lst.next return sorted(ret) |