LeetCode第21/23题:Merge Two Sorted Lists和Merge k Sorted Lists总结

题目一

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)

代码2(python)

题目二

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

  • 大意:明显是前一道题的升级版,这次是合并k个已排序列表到一个列表。

思路0:

其实,这个就是一个归并排序,和归并排序不同的是,归并排序开始我们需要假设所有顺序都是乱的,我们假定每一个数都是一个list,然后逐步减少list数目,加长每一个list长度,而这道题,相当于已经进行到一半的归并排序。
不过,这没有关系,因为归并是递归实现的,我们玩全可以按照归并的方法,做这道题,而且正好用到了上一个题的代码。

代码:(Python)

参考:
《百度百科 归并排序》( http://baike.baidu.com/link?url=V2OlIM61x3mTzbnICxp-CK5GD6CfSz1JHy4KWHLpcRbgd6LO8Nz9oYobdtF58Lat6-BfiB8F1NH2P49QW0vW9_ )

思路1:

用堆排序,用到了python的heapq这个数据结构。

代码(python):

思路2:

用python的排序,直接将所有列表的所有数放在一个列表中,然后直接用sorted()排序。
个人感觉:虽然投机取巧,但是速度一点也不慢,实际解决问题却最快速实用。

代码(Python):

发表评论

电子邮件地址不会被公开。 必填项已用*标注