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

# 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
        p1 = pHead1
        p2 = pHead2
		# 创建合并链表的头结点和指向头结点的指针，有头结点可以防止链表丢失
        pHead = ListNode(0)
        p = pHead
		# 注意：这里是and不是or，必须p1和p2都存在才能继续循环
        while p1 and p2:
			# 尾差法，如果p1的值小于p2
            if p1.val < p2.val:
				# 创建临时指针指向p1的下一个节点，防止链表丢失
                tmp = p1.next
				# 新链表的指向p1
                p.next = p1
				# p1的节点成为新链表最后一个节点
                p = p1
				# p1指回pHead1链表
                p1 = tmp
			# 思路与上同
            else:
                tmp = p2.next
                p.next = p2
                p = p2
                p2 = tmp
		如果p1存在，新链表最后一个节点指向p1
        if p1:
            p.next = p1
        elif p2:
            p.next = p2

        return pHead.next