打印两个有序链表的公共部分-python3

类似于堆排序的merge过程

实例化出两个链表（s1, s2）,比较连个链表当前元素的大小，谁小谁执行next()方法继续比较，当出现相当的时候把相等的值塞入数组$common里或者直接打印，当两个链表有一个元素比较完了，全部结束。

代码如下：

#coding=utf-8
'''
打印两个有序链表的公共部分
【 题目】 给定两个有序链表的头指针head1和head2， 打印两个
链表的公共部分。
'''

class Nodes(object):
    """单向链表的结点"""
    def __init__(self,elem):
        self.elem=elem
        self.next=None

class SingleLinkList(object):
    """单链表"""
    def __init__(self,node=None):
        """构造函数"""
        self.__head=node    #头节点
    def getHead(self):
        return self.__head
    def travel(self):
        """遍历链表"""
        cur=self.__head
        while cur!=None:
            print(cur.elem,end=" ")
            cur=cur.next
        print("")
    def add(self,item):
        """链表头部添加元素
        O(1)
        """
        node=Nodes(item)
        node.next=self.__head
        self.__head=node
def printCommonPart(head1,head2):
    print("Common Part:")
    while head1 and head2:
        if head1.elem<head2.elem:
            head1=head1.next
        elif head1.elem>head2.elem:
            head2=head2.next
        else:
            print(head1.elem,end=" ")
            head1=head1.next
            head2=head2.next
    print("")
if __name__=="__main__":
    s1 = SingleLinkList()
    s1.add(10)
    s1.add(9)
    s1.add(8)
    s1.add(7)
    s1.add(6)
    s1.add(5)
    s1.add(4)
    s1.add(3)
    s1.add(2)
    print("s1:")
    s1.travel()
    s2=SingleLinkList()
    s2.add(5)
    s2.add(4)
    s2.add(3)
    s2.add(2)
    s2.add(1)
    s2.add(0)
    print("s2:")
    s2.travel()
    printCommonPart(s1.getHead(),s2.getHead())

运行结果如下：