博客

考虑到递增关系，所以使用尾插法建表（把指针始终放在尾结点）。

def Merge2(A,B):
    p=A.head.next
    q=B.head.next
    C=LinkList()#建立一个空链表
    t=C.head#将指针始终放在尾结点（后面会进行修改，这里只是初始化）
    while p!=None and q!=None:#两个子表都没有遍历完的情况下就继续遍历
        if p.data<q.data:#把小的那个元素尾插进表C
            t.next=p
            t=p#在表C中把指针移动到下一位
            p=p.next#在表A中把指针移动到下一位
        else:#同理
            t.next=q
            t=q
            q=q.next
    t.next=None#将最后一个结点的next域设置尾none
    if p!=None:#一个表遍历完，直接接入剩下的那个表（因为剩下的那个表也是递增的），这个判断语句成立就代表遍历完的那个表的最大元素小于剩下的表的最小元素
        t.next=p
    if q!=None:#与上同理
        t.next=q
    return C
#时间复杂度O（m+n）