Вставить неупорядоченный связанный список в упорядоченный связанный список

Question

Недавно мне дали задание написать (а) эффективные, элегантные функции C, которые вставляют содержимое неупорядоченного связанного списка в упорядоченный связанный список.

Вот что я придумал:

node * insert(node * dest, node * src)
{
    node * current = dest;
    node * previous = NULL;

    //Deal with zero-length destination list
    if (dest == NULL) { return src; }

    //Deal with putting it at the start
    if (src->data >= dest->data)
    {
        src->next = dest;
        return src;
    }

    //Iterate to find the right position
    while (current->data <= src->data)
    {
        previous = current;
        current = current->next;
    }
    previous->next = src;
    src->next = current;
    return dest;
}

node * insertLL(node * sorted, node * unsorted)
{
    while(unsorted != NULL)
    {
        node * next_unsorted = unsorted->next;
        sorted = insert(sorted, unsorted);
        unsorted = next_unsorted;
    }

    return sorted;
}

Можете ли вы все критиковать мои функции - особенно, эффективна ли моя функция insert ()? Мне это кажется довольно большим.

Answer 1

Мне кажется, что ваш алгоритм просто вставляет каждый из несортированных элементов в отсортированный список по одному. Если у вас m не отсортировано и n отсортировано, это в основном даст вам количество операций, пропорциональное m * n.

Если бы вы создали массив несортированных элементов, а затем отсортировали их (m log m операции), вы могли бы затем использовать слияние (m + n операции) для создания нового списка.

Честно говоря, различия не обязательно станут очевидными, пока m и / или n не начнут становиться большими, но об этом нужно помнить.

---

Кроме того, я думаю, что вы также можете столкнуться с проблемами, когда несортированный элемент находится в конце отсортированного списка. У вас есть специальная обработка для начала, но если вы вставляете 7 в список {1,2,3}, вы в конечном итоге попытаетесь разыменовать NULL, потому что current вышел за пределы конца отсортированного списка (current->data <= src->data будет быть истинным для всех ненулевых значений current).