Сортировка слиянием связанного списка

Мне нужно отсортировать связанный список, используя сортировку слиянием. Я собрал этот код, но столкнулся со странной ошибкой.

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

Вот часть моего кода:

node* MergeSort(node *my_node)
{
    node *secondNode;

    if (my_node == NULL)
        return NULL;
    else if (my_node->next == NULL)
        return my_node;
    else
    {
        secondNode = Split(my_node);
        return Merge(MergeSort(my_node),MergeSort(secondNode));
    }
}

node* Merge(node* firstNode, node* secondNode)
{
    if (firstNode == NULL) return secondNode;
    else if (secondNode == NULL) return firstNode;
    else if (firstNode->number <= secondNode->number) //if I reverse the sign to >=, the behavior reverses
    {
        firstNode->next = Merge(firstNode->next, secondNode);
        return firstNode;
    }
    else 
    {
        secondNode->next = Merge(firstNode, secondNode->next);
        return secondNode;
    }
}

node* Split(node* my_node)
{
    node* secondNode;

    if (my_node == NULL) return NULL;
    else if (my_node->next == NULL) return NULL;
    else {
        secondNode = my_node->next;
        my_node->next = secondNode->next;
        secondNode->next = Split(secondNode->next);
        return secondNode;
    }
}

c++ mergesort linked-list
person xbonez    schedule 12.04.2011    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Я попробовал ваш код, и он отлично работает.

Вы смотрели на правильный список в конце? Ваш новый заголовок списка — это не предыдущий заголовок, а возвращаемое значение функции слияния.

printList(myList);
node* sortedList =  MergeSort(myList);
printList(sortedList); //whole list sorted
printList(myList); //list (of elements not smaller that first element) sorted

и printList() - очевидная функция:

void printList(node* my_node){
    if(my_node == NULL) return;
    else {
        std::cout<<my_node->number<<" "<<std::endl; 
        printList(my_node->next);   
    }
}
person tgmath    schedule 12.04.2011
comment
О да. Я вижу, где я ошибался. Спасибо. Это исправило это. - person xbonez; 12.04.2011