Простой merge_sort в списке - анализ

Question

Я написал простую функцию, которая объединяет два отсортированных списка в один. К сожалению, я не мог получить результат, я не знаю, почему. Компилятор не показывает никаких утверждений и прекращает работу при запуске функции. Кажется, я все в порядке. Проверьте это, пожалуйста. Ниже показан код.

node list_sort (node*& h, node*& h1, node*& h2) 
{ 
    if (h1 && h2 == NULL) 
    { 
     h = h1; 
     return *h; 
    } 

    if (h2 && h1 == NULL) 
    { 
     h = h2; 
     return* h; 
    } 

    if (h1 == NULL && h2== NULL) 
    { 
     h = NULL; 
     return* h; 
    } 

    if (h1 && h2) // condition required to set a head 
    { 
     if (h1->vol > h2->vol) 
      h = h2; 

     else 
      h = h1; 
    } 

    mode* p; 
    p = h; 

    while (h1 && h2) 
    { 
     if (h1->vol > h2->vol) 
     { 
      p->next = h2; 
      h2 = h2->next; 
     } 

     else 
     { 
      p->next = h1; 
      h1 = h1->next; 
     } 

     p = p->next; 
    } 

    if (h1) 
    { 
     while (h1) 
     { 
      p->next = h1; 
      h1 = h1->next; 
      p = p->next; 
     } 
    } 

    else 
    { 
     while (h2) 
     { 
      p->next = h2; 
      h2 = h2->next; 
      p = p->next; 
     } 
    } 

    h1 = NULL; 
    h2 = NULL; 
    return* h; 
} 

Answer 1

При назначении нового главы, вы должны заранее список вы берете его из:

if (h1 && h2) 
{ 
    if (h1->vol > h2->vol) { 
     h = h2; 
     h2 = h2->next; 
    } else { 
     h = h1; 
     h1 = h1->next; 
    } 
} 

В противном случае вы будете принимать один и тот же узел, скажем h1 снова в цикле while, но его next указатель h1. Ad infinitum ...

Условие if (h1 && h2) ... также избыточно, потому что вы рассматривали все другие случаи раньше. (Но вы должны установить исходные списки в NULL в этих случаях, чтобы поддерживать логику функции: Исходные списки израсходованы, все элементы теперь находятся в объединенном списке h.)

Обратите внимание: 't нужны последние две петли while: Остальная часть списка уже имеет правильные соединения. Вам нужно только установить:

p->next = (h1 != NULL) ? h1 : h2; 
h1 = NULL; 
h2 = NULL; 

Семантика вашей функции также необычна. Если вы передадите объединенный список в качестве ссылки, вам не нужно возвращать node. Вы могли бы вернуть новую голову, но это было бы лишним. Вы можете вернуть некоторую связанную информацию, скажем, счет объединенного списка, который вызывающий может игнорировать. Или просто сделайте функцию void.

Вы можете вернуть новую главу списка и оставить свой первый параметр:

node *list_merge(node *&h1, node *&h2) 
{ 
    node *h = NULL; 

    // merge list 

    return h; 
} 

Наконец, вы можете поймать все частные случаи, а также объединить if и while петли, когда вы строите свой новый список с указателем указатель узла:

node *list_sort(node *&h1, node *&h2) 
{ 
    node *h = NULL; 
    node **p = &h; 

    while (h1 && h2) { 
     if (h1->vol > h2->vol) { 
      *p = h2; 
      h2 = h2->next; 
     } else { 
      *p = h1; 
      h1 = h1->next; 
     } 
     p = &(*p)->next; 
    } 

    *p = h1 ? h1 : h2; 
    h1 = NULL; 
    h2 = NULL; 

    return h; 
} 

Вот и все, и вы получите лаконизм, используя один уровень косвенности: указатель на голову указателя заполняет голову h на своем первом распайке и next членов нового списка, как вы идете.