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

# 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
        if (pHead1 == None):
            return pHead2

        if (pHead2 == None):
            return pHead1
        
        new = ListNode(0) #初始虚拟节点
        p = new

        while (pHead1 and pHead2):
            if (pHead1.val <= pHead2.val):
                p.next = pHead1
                pHead1 = pHead1.next
                p = p.next

            else:
                p.next = pHead2
                pHead2 = pHead2.next
                p = p.next
        
        if (pHead1):
            p.next = pHead1

        if (pHead2):
            p.next = pHead2

        return new.next #去掉初始虚拟节点

初始版本如下，测试集不通过，输出皆为空。总体思路正确，但比较部分的思路，因为没有引入新链表而变得复杂。

对于空间复杂度O(1)，可引入另一空链表。

# 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
        if (pHead1 ==None):
            return pHead2

        if (pHead2 ==None):
            return pHead1

        while (pHead1 and pHead2 != None): # 可直接写为 while (pHead1 and pHead2):
            if (pHead1.val > pHead2.val):
                tmp1 = pHead1.next
                tmp2 = pHead2.next
                pHead1.next = pHead2
                pHead2.next = tmp1
                pHead1 = tmp1
                pHead2 = tmp2

            elif (pHead1.val <= pHead2.val):
                pHead1 = pHead1.next

            elif (pHead1 == None):
                pHead1.next = pHead2
            
            elif (pHead2 == None):
                pHead1.next = pHead1
            
        return pHead1