Мне нужно сделать эту функцию более эффективной

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) операция.