Объединить два отсортированных списка Python
Я пытаюсь решить проблему отсортированного связанного списка слиянием. Для этого я создал три метода. addlast , print and merge Для класса связанного списка создано три объекта obj and obj1 (To create two linked list) Использование obj3 вызова метода слияния путем передачи указателя на заголовок обоих связанных списков. Но здесь он печатает только linked list 1 вместо обоих.
Моим ожидаемым результатом должно быть создание как связанного списка, так и печать отсортированного связанного списка. Так в чем может быть причина, по которой мой код не работает?
class node:
def __init__(self,data) :
self.data = data
self.next = None
class linkedlist:
def __init__(self) :
self.head = None
def addlast(self,data):
newnode = node(data)
if self.head == None:
self.head = newnode
else:
current = self.head
while(current.next != None):
current = current.next
current.next = newnode
def print(self):
current = self.head
while(current):
print(current.data, "-->",end = "")
current = current.next
print("NUll")
def merge(self,obj,obj1):
current = obj.head
current2 = obj1.head
newnode = node(None)
while current and current2 != None:
if (current == None):
newnode.next = current2
break
if (current2 == None):
newnode.next = current
break
if current.data <= current2.data:
newnode.next = current
current = current.next
print(newnode.data)
newnode = newnode.next
else:
newnode.next = current2
current2 = current2.next
print(newnode.data)
newnode = newnode.next
if current:
newnode.next = current
if current2:
newnode.next = current2
print(newnode.data)
obj = linkedlist()
obj.addlast(10)
obj.addlast(20)
obj.addlast(30)
obj.addlast(40)
obj1 = linkedlist()
obj1.addlast(50)
obj1.addlast(60)
obj1.addlast(70)
obj1.addlast(80)
obj3 = linkedlist()
obj3.merge(obj,obj1)
Ответы 3
В функции слияния вы не обновляете переменную экземпляра self.head, ваш код объединяет список, но вы не отслеживаете заголовок. Измените функцию слияния кода, чтобы указать self.head на новый узел:
def merge(self,obj,obj1):
current = obj.head
current2 = obj1.head
newnode = node(None)
self.head=newnode
В вашем коде есть несколько проблем:
Вы создали
mergeкак метод экземпляра, но никогда не используетеself. Если вы намерены объединить второй список с текущим списком (self), вам нужен только один аргумент, то есть «другой» список, а не два.mergeдолжен установить атрибутheadсписка, который получает результат слияния, т. е.self.headдолжна быть назначена ссылка.newnodeпроходит через объединенный список, но ваш код теряет информацию о том, что было первым узлом этого объединенного списка, поэтому вам нужно дополнительное имя, чтобы вы могли позже назначитьself.headif (current == None)никогда не будет истинным условием, поскольку условиеwhileтребует, чтобы иcurrent, иcurrent2не былиNone. То же самое касаетсяif (current2 == None): это никогда не будет правдой.Код для связывания единственного оставшегося списка (последние два оператора
if) должен быть помещен после цикла, а не внутри него. Только после цикла становится ясно, что один изcurrentилиcurrent2равенNone. Также этот код можно упростить с помощью оператораor.Причина, по которой вы видите только напечатанную часть объединенного списка, заключается в том, что вы не печатаете узлы, которые добавляются («оптом») в этой последней операции.
Вот исправленный код:
def merge(self, obj1): # Only need one argument, not two
current = self.head # Use self
current2 = obj1.head
dummy = newnode = node(None) # keep track of this dummy node
while current and current2:
if current.data <= current2.data:
newnode.next = current
current = current.next
else:
newnode.next = current2
current2 = current2.next
newnode = newnode.next # This is common to both if/else case
newnode.next = current or current2 # out of the loop
self.head = dummy.next # update current list's head reference
Вызывающий код должен иметь ближе к концу:
obj.merge(obj1)
obj.print()
Это связывает 2 списка Studrec и Aves, а затем сортирует Studrec, извлекая соответствующие элементы из Ave.
def revert(Studrec, Ave):
Studrec, Ave = map(list, zip(*sorted(zip(Studrec, Ave), key=lambda x: x[0])))
return Studrec, Ave
Studrec, Ave = revert (Studrec, Ave)
Вы, конечно, не хотите устанавливать голову на новый узел, у которого нет данных.