Алгоритм подхода к объединению двух связанных списков - PullRequest
Новая
       64

Алгоритм подхода к объединению двух связанных списков

0 голосов
/ 12 февраля 2020

Какой алгоритм лучше объединить два отсортированных связанных списка по возрастанию в один отсортированный список по возрастанию?

Время против пространственной сложности?

Это решение уменьшает Пространственная сложность программы, поскольку новый связанный список не создается и не назначается излишне.

предполагается, что head1 и head2 - узлы заголовков списков 

if(head1==null && head2==null)  return null;
if(head1==null && head2!=null)  return head2;
if(head1!=null && head2==null)  return head1;

    //assigning mergeLists head to min of both head
    SinglyLinkedListNode t1, t2, c;
    if(head1.data<head2.data){
            t1 = head1;
            t2 = head2;
            c = head1;
    }else{
            t1 = head2;
            t2 = head1;
            c = head2;
    }

    //sorting both lists within without creating new list
    while(t1.next!=null){
            if(t1.next.data <= t2.data) t1 = t1.next;
            else{
            SinglyLinkedListNode temp = t1.next;
            t1.next = t2;
            t1 = t1.next;
            t2 = temp;
            }
    }
    t1.next = t2;
    return c;

Этот classi c рекурсивный подход лучше с точки зрения сложности времени.

принимает a как head1 и b как head2 

MergeSorted(Node a, Node b)
    if (a == null && b == null)
                return null;
            if a==null
                return b;
            if b==null
                return a;

            Node c //Combined List // new list
            if((a).data<(b).data)
                c=a;
                (c).next=MergeSorted((a).next,b);
            else
                c=b;
                (c).next=MergeSorted(a,(b).next);      
            return c;

1 Ответ

0 голосов
/ 12 февраля 2020

Ни один из них не создает новый список. c - это просто еще одна ссылка на узел списка, а не новый объект.

Ваш первый оператор, проверяющий оба списка на null, ничего не добавляет в программу: сразу следующий if сделает та же самая работа.

Ни один из них не превосходит по времени сложность ; каждый из них O (a + b) в двух длинах списка. Различия заключаются в ясности и ремонтопригодности. Поскольку вы не определили свою метри c как «лучше» в любых других терминах, вопрос спорный.

...