共计 1904 个字符，预计需要花费 5 分钟才能阅读完成。
合并两个有序链表
LeetCode21. 合并两个有序链表
问题形容
输出两个枯燥递增的链表，输入两个链表合成后的链表，咱们须要合成后的链表满足枯燥不减规定。
示例：
输出: {1,3,5},{2,4,6}
返回值: {1,2,3,4,5,6}
剖析问题
既然给定的两个链表都是有序的，那么咱们能够判断两个链表的头结点的值的大小，将较小值的结点增加到后果中，而后将对应链表的结点指针后移一位，周而复始，直到有一个链表为空为止。
因为链表是有序的，所以循环终止时，那个非空的链表中的元素都比后面曾经合并的链表中的元素大，所以，咱们只须要简略地将非空链表接在合并链表的前面，并返回合并链表即可。
首先咱们须要先创立一个哨兵节点，而后将 prehead 指向链表 l1 和 l2 中比拟小的一个。如果相等的话，指向任意一个即可。而后将较小值对应的链表的指针后移一位。
咱们上面来看一下代码实现。
def mergeTwoLists(self, l1, l2):
#合并后链表的哨兵结点
head=ListNode(-1,None)
pre=head
#循环遍历，将两个链表中的较小值插入到合并后的链表中
while l1 and l2:
if l1.val <= l2.val:
pre.next=l1
l1=l1.next
else:
pre.next=l2
l2=l2.next
pre=pre.next
#将残余的非空链表插入到合并链表的前面
if l1:
pre.next=l1
else:
pre.next=l2
return head.next其实，咱们这里也能够应用递归的形式来实现。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1, l2):
#链表 l1 为空，不须要合并，间接返回 l2
if(l1==None):
return l2
#同理，l2 为空，间接返回 l1 即可
if(l2==None):
return l1
if(l1.val<=l2.val):
l1.next=self.mergeTwoLists(l1.next,l2)
return l1
else:
l2.next=self.mergeTwoLists(l1,l2.next)
return l2问题降级
LeetCode23. 合并 K 个升序链表
上面，咱们来把问题降级一下，将两个有序链表合并改成多个有序链表合并，咱们来看一下题目。
给定一个有序链表，其中每个节点也示意有一个有序链表。结点蕴含两个类型的指针：
- 指向主链表中下一个结点的指针。
- 指向以此结点为头的链表。
示例如下所示：
4 -> 9 -> 15 -> 19
| | | |
7 13 18 28
| | |
8 21 37
|
20
实现函数 flatten()，该函数用来将链表扁平化成单个链表。例如下面的链表，输入链表为
4 -> 7 -> 8 -> 9 -> 13 -> 15 -> 18 ->19 -> 20 -> 21 -> 28 -> 37 题目要求咱们把二维有序链表合并成一个单链表，咱们来把问题简化一下，假如主链表只有两个节点，即这个二维链表变成如下所示。
4 -> 9
| |
7 13 旋转一下 4 -> 7 -> 8 -> 20
| ----------> |
8 9 -> 13
|
20 这不就是咱们下面讲的两个有序链表合并吗？那如果主链表有多个节点呢？咱们能够应用归并的思维，一一去合并就好了，如下图所示。
上面咱们来看一下代码如何实现。
class ListNode:
def __init__(self, val=0, right=None, down=None):
self.val = val
self.right = right
self.down = down
class Solution:
def mergeTwoLists(self, l1, l2):
#如果有一个链表为空，则合并后的链表就是另外一个
if(l1==None):
return l2
if(l2==None):
return l1
if(l1.val<=l2.val):
l1.down=self.mergeTwoLists(l1.down,l2)
return l1
else:
l2.down=self.mergeTwoLists(l1,l2.down)
return l2
def flatten(self,root):
if root== None or root.right == None:
return root
#把 root->right 看作是曾经有序的单链表，#而后通过递归来进行归并
return self.mergeTwoLists(root, self.flatten(root.right))更多算法题解，请关注公众号《程序员学长》，欢送大家退出
正文完
