將無序鏈接列表插入到有序鏈接列表中

我最近接到一個挑戰，要編寫一個有效，優雅的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

將無序鏈接列表插入到有序鏈接列表中

回答

相關問題