Python 单链表合并算法：将两个升序单链表合并为一个升序单链表

#################################################################
#类名称：Node
#类说明：定义一个结点类
#类释义：创建一个结点类，类中包含数值域与指针域
#################################################################
class Node(object):   
    #####################################
    #初始化结点函数
    ##################################### 
    def __init__(self,data):
        self.data=data
        self.next=None

#################################################################
#类名称：SingleLinkedList
#类说明：定义一个单链表
#类释义：创建一个单链表，并对其执行相关操作
#################################################################
class SingleLinkedList(object):
    #####################################
    #初始化头结点函数
    ##################################### 
    def __init__(self):
        self.head=Node(None)
    #####################################
    #创建单链表函数
    ##################################### 
    def CreateSingleLinkedList(self):
        print('***************************************************')
        print('*请输入数据后按回车键确认，若想结束输入请按“#”。*')
        print('***************************************************')
        cNode=self.head
        Element=input('请输入当前结点的值：')
        while Element!='#':
            nNode=Node(int(Element))
            cNode.next=nNode
            cNode=cNode.next
            Element=input('请输入当前结点的值：')    
    #####################################
    #尾端插入函数
    ##################################### 
    def InsertElementInTail(self):
        Element=(input('请输入待插入结点的值：'))
        if Element=='#':
            return
        cNode=self.head
        nNode=Node(int(Element))
        while cNode.next!=None:
            cNode=cNode.next
        cNode.next=nNode
    #####################################
    #首端元素函数
    ##################################### 
    def InsertElementInHead(self):
        Element=input('请输入待插入结点的值：')
        if Element=='#':
            return
        cNode=self.head
        nNode=Node(int(Element))
        nNode.next=cNode.next
        cNode.next=nNode
    #####################################
    #获取单链表长度函数
    ##################################### 
    def GetLength(self):
        cNode=self.head
        length=0
        while cNode.next!=None:
            length=length+1
            cNode=cNode.next
        return length    
    #####################################
    #判断单链表是否为空函数
    ##################################### 
    def IsEmpty(self):
        if self.GetLength()==0:
            return True
        else:
            return False                     
    #####################################
    #查找指定元素并返回其位置函数
    ##################################### 
    def FindElement(self):
        Pos=0
        cNode=self.head
        key=int(input('请输入想要查找的元素值：'))
        if self.IsEmpty():
            print('当前单链表为空！')
            return      
        while cNode.next!=None and cNode.data!=key:
            cNode=cNode.next
            Pos=Pos+1
        if cNode.data==key:
            print('查找成功，值为',key,'的结点位于该单链表的第',Pos,'个位置。')
        else:
            print('查找失败！当前单链表中不存在含有元素',key,'的结点')
    #####################################
    #删除元素函数
    ##################################### 
    def DeleteElement(self):
        dElement=int(input('请输入待删除结点的值：'))
        cNode=self.head
        pNode=self.head
        if self.IsEmpty():
            print('当前单链表为空！')
            return
        while cNode.next!=None and cNode.data != dElement:
            pNode=cNode
            cNode=cNode.next
        if cNode.data==dElement:
            pNode.next=cNode.next
            del cNode
            print('成功删除含有元素', dElement,'的结点')
        else:
            print('删除失败！当前单链表中不存在含有元素', dElement,'的结点')
    #####################################
    #遍历单链表某一结点函数
    ##################################### 
    def VisitElement(self,tNode):
        if tNode!=None:
            print(tNode.data,'->',end='')
        else:
            print('None')
    #####################################
    #遍历单链表函数
    ##################################### 
    def TraverseElement(self):
        cNode=self.head
        if cNode.next==None:
            print('当前单链表为空！')
            return
        print('您当前的单链表为：')
        while cNode!=None:
            cNode=cNode.next
            self.VisitElement(cNode)         

##############################
#创建单链表类LinkListA和LinkListB
##############################
LinkListA=SingleLinkedList()
LinkListB=SingleLinkedList()
###############
#创建单链表A
###############
print('请创建单链表A：')
LinkListA.CreateSingleLinkedList()
###############
#遍历单链表A
###############
LinkListA.TraverseElement()
###############
#尾端插入元素
###############
LinkListA.InsertElementInTail()
###############
#遍历单链表A
###############
LinkListA.TraverseElement()
###############
#首端插入元素
###############
LinkListA.InsertElementInHead()
###############
#遍历单链表A
###############
LinkListA.TraverseElement()
###############
#查找结点指定位置
###############
LinkListA.FindElement()
###############
#删除指定位置结点
###############
LinkListA.DeleteElement()
###############
#遍历单链表A
###############
LinkListA.TraverseElement()

###############
#创建单链表B
###############
print('请创建单链表B：')
LinkListB.CreateSingleLinkedList()
###############
#遍历单链表B
###############
LinkListB.TraverseElement()
###############
#尾端插入元素
###############
LinkListB.InsertElementInTail()
###############
#遍历单链表B
###############
LinkListB.TraverseElement()
###############
#首端插入元素
###############
LinkListB.InsertElementInHead()
###############
#遍历单链表B
###############
LinkListB.TraverseElement()
###############
#查找结点指定位置
###############
LinkListB.FindElement()
###############
#删除指定位置结点
###############
LinkListB.DeleteElement()
###############
#遍历单链表B
###############
LinkListB.TraverseElement()

##############################
#将单链表B合并进单链表A中
##############################
def merge_sorted_linked_lists(head1, head2):
    dummy = Node(None)
    tail = dummy
    while head1 is not None and head2 is not None:
        if head1.data <= head2.data:
            tail.next = head1
            head1 = head1.next
        else:
            tail.next = head2
            head2 = head2.next
        tail = tail.next

    # 连接剩余节点
    if head1 is not None:
        tail.next = head1
    if head2 is not None:
        tail.next = head2

    return dummy.next

# 合并单链表A和单链表B
LinkListA.head = merge_sorted_linked_lists(LinkListA.head, LinkListB.head)

##############################
#输出合并后的单链表
##############################
print('合并后的单链表为：')
LinkListA.TraverseElement()