c - 我需要让这个功能更有效率

Question

我现在的函数是 O(n)。它通过获取第一个列表并将其反转，然后将其放回第二个列表的前面来附加两个列表类型的结构。我不知道如何将我当前拥有的功能附加到这两个列表中。有谁知道我怎样才能做到 O(1)？

我目前的想法是，也许我必须制作一个完全不同的功能。

追加函数:

ilist iappend_destroy(ilist il1, ilist il2){
   if(il1 == NULL && il2 == NULL){
      free(il1);
      free(il2);
      return NULL;
   }else if(il1 == NULL){
      free(il1);
      return(il2);
   }else if(il2 == NULL){
      free(il2);
      return(il1);
   }else{

   ilist tmp = iempty();
   ilist clone = il1;

   while(il1 != NULL){
      tmp = icons_destroy(il1->first, tmp);
      il1 = il1->rest;
   }

   ilist tmpclone = tmp;

   while(tmp != NULL){
      il2 = icons_destroy(tmp->first, il2);
      tmp = tmp->rest;
   }

   idelete(tmpclone);
   idelete(clone);
   return il2;
   }

附加函数正在使用的图标函数:

ilist icons_destroy(int in, ilist il){
   if (il == NULL) {
      ilist anewlist = malloc(sizeof(struct ilist_ADT));
      anewlist->first = in;
      anewlist->rest = NULL;
      return (anewlist);
   } else {
      ilist previous = malloc(sizeof(struct ilist_ADT));
      previous->first = il->first;
      previous->rest = il->rest;
      il->first = in;
      il->rest = previous;
      return il;
   }
}

Answer 1

假设要附加的原始列表正在被销毁，就像您的代码中的情况一样，您可以使用以下算法在 O(1) 中附加两个列表:

lAend ----------------------------+
                                  V
listA -> item A1 -> item A2 -> item A3 -> null
listB -> item B1 -> item B2 -> item B3 -> null
                                  ^
lBend ----------------------------+

您需要列表结束指针和列表开始指针，但是将 listB 附加到 listA 末尾的代码很简单:

lAend->next = listB; lAend = lBend;
listB = null;        lBend = null;

之后，listB 为空，listA 包含组合列表:

lAend ---------------------------------------+
listA -> item A1 -> item A2 -> item A3 --+   |
                                         |   |
                +------------------------+   |
                |                            V
                +--> item B1 -> item B2 -> item B3 -> null
listB -> null
lBend -> null

如果您不存储结束指针，O(1) 是不可能的，因为您需要找到第一个列表的最后一个元素，从根本上讲O(n) 操作。