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

# 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 not pHead1:  # 如果链表1为空
            return pHead2  # 返回链表2
        elif not pHead2:  # 否则判断如果链表2为空
            return pHead1  # 返回链表1
        # 此时排除了两个链表有任意一个为空的情况，接下来处理都不为空
        head1 = pHead1
        curr1 = head1  # 链表1用来比较的节点初始化
        curr2 = pHead2  # 链条2用来比较的节点初始化
        prev1 = None
        # 整体逻辑：
        # 将链表2中的节点于链表1中的节点挨个比较
        # 如果在两者之间或者比链表1最小的都小就放进链表1然后比较下一个
        # 如果链表2的节点比链表1最小的都小，那就要更新链表1的头节点
        # 如果比链表1最大的都大，就可以不用再比较了，直接接入最后即可
        # 返回链表1的开头即可
        while curr2:
            next_node2 = curr2.next
            while curr1:
                if not prev1:  # 如果prev1为None
                    if curr2.val <= curr1.val:  # curr2更小
                        # 将curr2接入链表1中
                        curr2.next = curr1  #把curr2接上链表1的开头
                        curr1 = curr2  # 把curr1更新为curr2的值
                        head1 = curr2  # 把链表1的头节点更新为curr2
                        break
                    else:  # 比链表1最小的大
                        # 进入下一个循环，判断是否中间或更大
                        # 将链表1的prev和curr向后移动一位
                        prev1 = curr1
                        curr1 = curr1.next
                else:  # 如果prev1不为None
                    if prev1.val <= curr2.val <= curr1.val:
                        # 如果curr2在链表1的两者之间，那么将curr2加入链表1
                        prev1.next = curr2
                        curr2.next = curr1
                        prev1 = curr2 #更新prev1
                        break
                    else:  # curr2不在链表1两者之间
                        # 将链表1的prev和curr向后移动一位
                        prev1 = curr1
                        curr1 = curr1.next
                if not curr1:
                    prev1.next = curr2
            if not curr1:
                break
            curr2 = next_node2
        return head1