Блог

Я смотрю на сортированный связанный список слияния 2 в обратном порядке. Практическая задача для вундеркиндов для вундеркиндов:

Даны два связанных списка размера N и M , которые отсортированы в неубывающем порядке. Задача состоит в том, чтобы объединить их таким образом, чтобы результирующий список был в порядке убывания.

Ввод:

Первая строка входных данных содержит количество тестовых наборов T. Для каждого тестового набора первая строка входных данных содержит [sic] длину обоих связанных списков N и M соответственно. Следующие две строки содержат N и M элементов двух связанных списков.

Выход:

Для каждого тестового набора распечатайте объединенный связанный список, который находится в порядке возрастания.

Задача пользователя:

Задача состоит в том, чтобы завершить функцию mergeResult() , которая ссылается на заголовки обоих связанных списков и возвращает указатель на объединенный связанный список.

Мой Подход

Я пытаюсь сначала объединить список в порядке возрастания, а затем изменить его. Он работает для большинства тестовых случаев, но не работает для немногих с ошибкой:-

строка 21, в результате слияния

 p3=p3.next
 

Ошибка атрибута: объект «Нетип» не имеет атрибута «следующий»

 def mergeResult(h1,h2):
    p1=h1
    p2=h2
    node=Node(-1)
    p3=node
    while p1!=None and p2!=None:
        if p1.data<p2.data:
            p3.next=p1
            p1=p1.next
        elif p2.data<p1.data:
            p3.next=p2
            p2=p2.next
        p3=p3.next
    if p1!=None:
        p3.next=p1
    if p2!=None:
        p3.next=p2
    head=node.next
    curr=head
    prev=None
    next=None
    while curr:
        next=curr.next
        curr.next=prev
        prev=curr
        curr=next
    head=prev
    return head
 

Что я здесь делаю не так? Есть ли какой — либо другой подход к этой проблеме?

Проблема заключается в этой строке:

 elif p2.data<p1.data:
 

Здесь не должно быть условия, так как вы хотите разобраться со всеми оставшимися случаями. Прямо сейчас вы не рассматриваете случай, когда p2.data равно p1.data . Поэтому измените приведенную выше строку на:

 else:
 

Это устранит проблему.

Альтернатива

Существует более короткий способ достижения результата: вместо того, чтобы изменять список на втором этапе, вставляйте узлы непосредственно в обратном порядке. Таким образом, вы можете выполнять работу в одном цикле вместо двух. Затем вы должны продолжать цикл до тех пор , пока одна из ссылок отсутствует None , поэтому while условие становится or . Тогда в том if состоянии, в котором вам нужно учитывать, что одно из двух может быть None . Наконец, вам действительно не нужно вводить p1 p2 переменные и: просто используйте уже заданные h1 и h2 .

Это решение также не нуждается во временном узле «страж» (со значением -1).

 def mergeResult(h1,h2):
    result = None
    while h1 or h2:
        if not h2 or (h1 is not None and h1.data < h2.data):
            h1.next, result, h1 = result, h1, h1.next
        else:
            h2.next, result, h2 = result, h2, h2.next
    return result
 

Поэтому здесь h1 (или h2 ) добавляется к текущему списку результатов. После того, как он добавлен, ссылка на результат помещается в этот добавленный узел. Множественное назначение таково, что h1 (или h2 ) все равно перейдет к (исходному) следующему узлу, прежде next чем ссылка на этот узел будет скорректирована. Вы, конечно, можете также сделать это с отдельными назначениями, но тогда вам понадобится временная переменная:

 def mergeResult(h1,h2):
    result = None
    while h1 or h2:
        if not h2 or (h1 is not None and h1.data < h2.data):
            nxt = h1.next
            h1.next = result
            result = h1
            h1 = nxt
        else:
            nxt = h2.next
            h2.next = result
            result = h2
            h2 = nxt
    return result
 

В цикле while mergeResult вам нужно проверить, является ли p1.data == p2.data. В настоящее время вы не проверяете это, поэтому, когда p1.data == p2.data, p3.next не установлен (и, следовательно, сохраняет значение по умолчанию None). Это означает, что для p3 устанавливается значение None, и, как показывает ошибка, p3.next (т. е. None.next) не работает.