c-将无序链表插入有序链表中

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的所有非NULL值的current->data <= src->data都为true）。