题解 | #合并两个排序的链表#

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        solderNode = cur = ListNode(0)
        if pHead1 is None:
            return pHead2
        if pHead2 is None:
            return pHead1

        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
        cur.next = pHead1 or pHead2
        return solderNode.next

头插法

首先设置一个哨兵节点，solderNode 同是cur也代表solderNode solderNode 来作为新的listlink的head 开始串接各部分

首先判断边界条件 if phead1 is None: 注意要return phead2 ； if phead2 is None 要 return phead1

然后当phead1和phead2都不为None时 才进入循环：

开始进行两个链表的值的比对， phead1是listlink1的head，phead2 是 listlink2 的head，所以phead1.val是listlink1的第一个节点的值，phead2.val 是listlink2的第一个节点的值，先比较两个链表的第一个节点值的大小，if phead1.val <= phead2.val

说明phead1的第一个节点的值较小，用新的listlink进行串接应该先串phead1的第一个节点：cur.next = phead1让后移动phead1至listlink1的下一个节点：phead1 = phead1.next。

那么如果phead1.val>phead2.val 即else：也就是说更小的值是phead2，那么此时新的listlink首先应该串接phead2：cur.next = phead2, 然后phead2也移动到listlink2的下一个位置：phead2 = phead2.next

那么经过第一轮循环，我们已经穿好了新的listlink的第二个节点，（第一个节点是我们定义的solderNoder）。然后我们要让cur也移动到下一个节点的位置即第二个节点上 cur = cur.next. 等所有的循环都执行完了之后此时的cur是指向none的，而我们又需要让cur指回到正确的新的listlink的head，于是cur.next = phead1 or phead2

最后返回的时候因为我们新的listlink第一个节点是我们定义的solderNode所以应该返回solder.next