非递归法

链表A：A1->A2->A3->...->An

链表B：B1->B2->B3->...->Bm

创建一个表头节点head，将链表A和链表 B的表头较小的节点，依次加入到表头head后面，直到链表A或B有一方到达末尾，最后将未到达末尾的剩余链表，直接拼接到head最后

# 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
        # 表头
        p = head = ListNode(0)
        # 任一条链表结束，则停止
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                p.next = pHead1
                pHead1 = pHead1.next
            else:
                p.next = pHead2
                pHead2 = pHead2.next
            p = p.next
        # 将长度不为0的剩余链表，直接拼接到最后
        if pHead1:
            p.next = pHead1
        else:
            p.next = pHead2
        return head.next