将无序链接列表插入到有序链接列表中

我最近接到一个挑战，要编写一个有效，优雅的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; 
}

大家可以批评我的功能 - 我的插入（）函数，尤其是是否是有效的？这对我来说似乎相当大。

来源

2011-06-16 Adam S

按**命令**你其实是指**排序**吗？因为链表总是有序的（它们的元素总是按照某种顺序）。 – Jesper 2011-06-16 07:07:27

在我看来，你的算法只是每次将一个未排序的元素插入排序列表中。如果你有m未分类和n排序，这基本上会给你一个与m * n成正比的操作计数。

如果您要创建未排序项目的数组然后对它们进行排序（m log m操作），则可以使用合并（m + n操作）构造一个新列表。

说实话，差异并不一定会变得明显，直到m和/或n开始变大，但需要牢记。

顺便说一句，我想你也可能会碰到的问题，其中未分类的项目属于在末排序列表的。开始时您有特殊的处理，但是如果您将7插入列表{1,2,3}，则最终会尝试解除空值，因为current已排出排序列表的末尾（current->data <= src->data将为真全部 non- NULL值current）。

来源

2011-06-16 06:57:18 paxdiablo

将无序链接列表插入到有序链接列表中

回答

相关问题