Разрешить дублирование в сортировке слиянием в односвязном списке C ++

Question

Меня это сейчас очень раздражает.Я изучаю сортировку слиянием для университетов и прохожу через этот сортировку слиянием , которую я нашел в сети.Тем не менее, я, кажется, не получаю дубликаты, и я хочу дубликаты.Этот бит выглядит следующим образом, но я прокомментировал этот бит и прочее, и это заставило сортировку работать неправильно.Можно ли как-нибудь сохранить дубликаты?Я был бы признателен, если бы вы могли оставить ответы простыми.Спасибо

else
{
    // Both are equal.
    // Arbitraritly chose to add one of them and make
    // sure you skip both!


    if(c == NULL)
    {
        c = a;
    }
    else
    {
        c->next = a;
        c = c->next;
    }

    a = a->next;
    b = b->next;
}

Answer 1

Если вы хотите сохранить дубликаты, добавьте оба в связанный список c.Прямо сейчас вы добавляете только один (например, a или b) в связанный список.

Поэтому измените свой код так:

temp_a_next = a->next;
temp_b_next = b->next;

if(c == NULL)
{
    c = a;
    c->next = b;
    c = b;
}
else
{
    c->next = a;
    c = a;
    c->next = b;
    c = b;
}

a = temp_a_next;
b = temp_b_next;

Еще одинпримечание: конечный заголовок отсортированного списка с дубликатами будет иметь начальную точку в a, так как к концу этого алгоритма c будет указывать на конец списка, и этот алгоритм фактически изменяет указателиузлы a и b (т. е. c не является новым связанным списком с новыми узлами).

Answer 2

Вы можете исключить третий случай (текущий блок else, указанный в коде) и изменить второй случай с a > b на else - теперь он будет обрабатывать любой случай, где a >= b, и всегда будет помещатьa первый в отсортированном списке.

Answer 3

Я думаю, что подсказка в комментарии в коде: " убедитесь, что вы пропустили оба ".Увеличивая оба указателя списка, вы добавляете один элемент к выводу, но пропускаете два элемента ввода.Так что увеличивайте только один указатель.Затем другой элемент будет перемещен в список вывода на следующей итерации.