我怎样才能在O（n）复杂度下实现这一点？

Question

我正在做一个与新冠病毒相关的大学项目

class Patient:
"""Class to represent a Patient"""
def __init__(self,name,year,covid,vaccine):
    self.name=name
    self.year=year
    self.covid=covid
    self.vaccine=vaccine
    
def __str__(self):
    return self.name+'\t'+str(self.year)+'\t'+str(self.covid)+'\t'+str(self.vaccine)



class HealthCenter(DList):
"""Class to represent a Health Center"""
def __init__(self,filetsv=None):
    super(HealthCenter, self).__init__()

    if filetsv is None or not os.path.isfile(filetsv):
        self.name=''

    else: 
        print('loading the data for the health center from the file ',filetsv)

        self.name=filetsv.replace('.tsv','')
        tsv_file = open(filetsv)
        read_tsv = csv.reader(tsv_file, delimiter="\t")


        for row in read_tsv:
            name=row[0]
            year=int(row[1])
            covid=False
            
            if int(row[2])==1:
                covid=True

            vaccine=int(row[3])
            self.addLast(Patient(name,year,covid,vaccine))

所以我必须创建一个方法“merge”，它接受一个参数“other”，这是另一个HealthCenter，HealthCenter是链表，它们的元素是patients。 所以merge必须返回一个新的HealthCenter，其中包含来自两个healthcents的患者，按字母顺序排序，如果两个中心都有相同的患者（相同的名称），只需添加一次即可。（中心已按字母顺序排序） 我不能使用python列表，也不能使用字典等。只允许使用喜欢的列表、堆或队列，我必须以O（n）的复杂性来完成

我首先想到的是一段时间后比较名字，但不是O（n）。我还把所有的名字都放在一个字符串中，并将它们放在一个while循环中进行比较。。。但后来我发现它也不是O（n）

def merge(self,other):
    """Junta los pacientes de dos centros y lo devuelve"""
    
    #Se copia uno de los dos centros y se juntan todos los nombres en un str
    nuevo1 = HealthCenter()
    copiador = self._head
    nombres = ""
    while copiador != None:
        nombres += copiador.elem.name
        nuevo1.addLast(copiador.elem)
        copiador = copiador.next
        
    #Se hace un conjunto sin ordenar pero ya quitando los repetidos  
    aux1 = other._head
    while aux1:
        #Solo se añade si no está ya el mismo paciente
        if aux1.elem.name not in nombres:
            nuevo1.addLast(aux1.elem)
        aux1 = aux1.next
        
    #Se crea el centro final
    nuevo2 = HealthCenter()
    
    elegido = nuevo1._head
    sig = elegido.next
    index = 0
    count = 1
    while elegido != None:
        
        
        #Si es menor, el elegido no cambia 
        # if elegido.elem.name < sig.elem.name:
        #     pass
        #Si es mayor, el elegido cambia al nuevo, que es más pequeño
        if sig != None: 
            if elegido.elem.name > sig.elem.name:
                elegido = sig
                index = count

            sig = sig.next
            count += 1
        #Cada vez que llega al final añade al elegido y vuelve a empezar 
        if sig == None:
            nuevo2.addLast(elegido.elem)
            count = 1
            nuevo1.removeAt(index)
            #Cuando solo quede un elemento, sig será None y volvera a entrar
            #en el if
            index = 0
            elegido = nuevo1._head
            if elegido != None:
                sig = elegido.next
            
    return nuevo2

有点糟糕的ikr程序，只是为了展示我的尝试

提前谢谢