python 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        p1 = l1
        p2 = l2
        # 引入虚拟头节点,并依次拼接
        head = ListNode()
        tail = head
        while p1 and p2:
            if p1.val <= p2.val:
                tail.next = p1
                tail = p1
                p1 = p1.next
            else:
                tail.next = p2
                tail = p2
                p2 = p2.next
        if p1:
            tail.next = p1
        if p2:
            tail.next = p2
        return head.next