合并两个排序的单链表
1 问题
关于链表的合并，常见的类型有两种：
- 直接合并，没有什么规则： 将多个链表头尾相连合并成一个链表
- 有序链表合并成有序链表： 两个有序链表合并成一个有序链表。
这里我们将要解决的问题是有序列表的合并，在上课的时候我们学习了如何直接合并两个单链表，那么如果在合并的同时还要注意顺序问题的话该如何解决呢？本篇周博客将讨论此问题。
2 方法
（1）判断空链表的情况，只要有一个链表为空，那答案必定就是另一个链表了，就算另一个链表也为空。
（2）新建一个空的表头后面连接两个链表排序后的节点，两个指针分别指向两链表头。
（3）遍历两个链表都不为空的情况，取较小值添加在新的链表后面，每次只把被添加的链表的指针后移。
（4）遍历到最后肯定有一个链表还有剩余的节点，它们的值将大于前面所有的，直接连在新的链表后面即可通过实验、实践等证明提出的方法是有效的，是能够解决开头提出的问题。
代码清单 1
Courier New字体，23磅行间距
鼠标右键，选择无格式粘贴。
def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
# write code here
#一个已经为空了，直接返回另一个
if pHead1 == None:
return pHead2
if pHead2 == None:
return pHead1
#加一个表头
head = ListNode(0)
cur = head
#两个链表都要不为空
while pHead1 and pHead2:
#取较小值的节点
if pHead1.val <= pHead2.val:
cur.next = pHead1
#只移动取值的指针
pHead1 = pHead1.next
else:
cur.next = pHead2
#只移动取值的指针
pHead2 = pHead2.next
#指针后移
cur = cur.next
#哪个链表还有剩，直接连在后面
if pHead1:
cur.next = pHead1
else:
cur.next = pHead2
#返回值去掉表头
# return head.next3 结语
我们针对排序单链表的合并问题，提出建新表及其他本篇博客涉及到的方法，通过代码运行成功证明该方法是有效的，本文的方法还有许多不足以及考虑不周的地方，希望通过未来的学习来改进。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2024-02-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读