python面试之python两个有序链表合并成一个有序链表

python两个有序链表合并成一个有序链表

class Node:
    def __init__(self,data=None):
        self.data=data
        self.next=None

class ListNode:
    def __init__(self):
        self.head=Node()

    def append(self,num):
        node=Node(num)
        cur=self.head
        while cur.next!=None:
            cur=cur.next
        cur.next=node

    def print(self):
        cur=self.head
        while cur.next!=None:
            print('data:',cur.data)
            cur=cur.next
        print('end:',cur.data)

def mergeList(head:ListNode,head2:ListNode):
    head1=head.head.next
    head2=head2.head.next
    newList=ListNode()
    while head1!=None and head2!=None:
        if head1.data<head2.data:
            newList.append(head1.data)
            head1=head1.next
        elif head1.data>head2.data:
            newList.append(head2.data)
            head2=head2.next
        else:
            newList.append(head1.data)
            newList.append(head2.data)
            head1=head1.next
            head2=head2.next

    if head1==None and head2!=None:
        while head2!=None:
            newList.append(head2.data)
            head2=head2.next

    if head1!=None and head2==None:
        while head1!=None:
            newList.append(head1.data)
            head1=head1.next
    return newList

if __name__ == '__main__':
    list=ListNode()
    list2=ListNode()
    list.append(1)
    list.append(3)
    list.append(5)
    list2.append(2)
    list2.append(4)
    list2.append(6)

    result=mergeList(list,list2)
    result.print()