Удаление каждого нечетного позиционированного узла в связанном списке в C

Я пытался создать функцию на C, которая удаляет каждый нечетный позиционированный узел. Например, 1,2,3,4 становится 2,4 .

Вот что я пробовал, но он, похоже, не работает. Я говорю о функции deletee . Я изменил его, но список, похоже, не меняется.

 #include  #include  typedef struct node { int val; struct node *next; } node; typedef struct ll { node *head; } ll; ll *newll() { ll *k = malloc(sizeof(ll)); k->head = NULL; return k; } void insert(ll *l, int vl) { node *tmp = malloc(sizeof(node)); tmp->next = NULL; tmp->val = vl; if (l->head == NULL) { l->head = tmp; return; } node *s = l->head; while (s->next != NULL) s = s->next; s->next = tmp; } void printll(ll *l) { node *s = l->head; while (s != NULL) { printf("%d ", s->val); s = s->next; } } void deletee(ll *l) { node *k = l->head; while (k != NULL && k->next != NULL) { node *tmp = k->next->next; k = tmp; } } int main() { ll *ll1 = newll(); insert(ll1, 5); insert(ll1, 6); insert(ll1, 8); insert(ll1, 9); insert(ll1, 10); insert(ll1, 11); deletee(ll1); printll(ll1); return 0; } 

Нам нужно будет обновить как ll.head , так и node.next , поэтому указатель на node недостаточно хорош, если вы не хотите, чтобы в специальном случае была голова. Вместо этого давайте использовать указатель на указатель, который мы хотим обновить.

 void delete_node(node** node_ptr_ptr) { node* to_delete = *node_ptr_ptr; *node_ptr_ptr = to_delete->next; free(to_delete); } void delete_every_second(ll* l) { node** node_ptr_ptr = &( l->head ); while (1) { if (*node_ptr_ptr == NULL) break; delete_node(node_ptr_ptr); if (*node_ptr_ptr == NULL) break; node_ptr_ptr = &( (*node_ptr_ptr)->next ); } } 

Скажем, вы начинаете со следующего:

 +------+ +------+ +------+ +------+ | head ------>| val | +-->| val | +-->| val | +------+ +------+ | +------+ | +------+ | next ---+ | next ---+ | next --->NULL +------+ +------+ +------+ 

После node** node_ptr_ptr = &( l->head ); :

 +------+ +------+ +------+ +------+ | head ------>| val1 | +-->| val2 | +-->| val3 | +------+ +------+ | +------+ | +------+ ^ | next ---+ | next ---+ | next --->NULL | +------+ +------+ +------+ | +-----+ | +------+ | | ptr ----+ +------+ 

После node* to_delete = *node_ptr_ptr; :

  +------+ | del ----+ +------+ | | +------+ | v +------+ +------+ +------+ +------+ | head ------>| val1 | +-->| val2 | +-->| val3 | +------+ +------+ | +------+ | +------+ ^ | next ---+ | next ---+ | next --->NULL | +------+ +------+ +------+ | +-----+ | +------+ | | ptr ----+ +------+ 

После *node_ptr_ptr = to_delete->next; free(to_delete); *node_ptr_ptr = to_delete->next; free(to_delete); :

 +------+ +------+ +------+ | head -------------------->| val2 | +-->| val3 | +------+ +------+ | +------+ ^ | next ---+ | next --->NULL | +------+ +------+ | +-----+ | +------+ | | ptr ----+ +------+ 

После node_ptr_ptr = &( (*node_ptr_ptr)->next ); :

 +------+ +------+ +------+ | head -------------------->| val2 | +-->| val3 | +------+ +------+ | +------+ +---------------->| next ---+ | next --->NULL | +------+ +------+ | +------+ | | ptr ----+ +------+ 

в этом коде:

 while(k!=NULL) { if(k->next!=NULL && k->next->next!=NULL) k->next=k->next->next; } в while(k!=NULL) { if(k->next!=NULL && k->next->next!=NULL) k->next=k->next->next; } 

у вас бесконечный цикл, так как вы не изменяете значение k в цикле.

Также: вам нужно будет удалить / освободить память для k->next сначала, или вы получите утечку памяти.

Я бы переписал его просто следующим образом:

 void deletee(ll *l) { if (l->head == NULL) return; node* tmp = l->head; l->head = l->head->next; // skip first item free(tmp); node* k=l->head; while(k!=NULL && k->next!=NULL) { tmp = k->next; k->next = k->next->next; free(tmp); k = k->next; } } 

результат (как и ожидалось):

 6 9 11 
  • tmp сохраняет следующее значение для последующего удаления
  • мы добавляем следующий элемент к следующему элементу элемента be-be-deleted, чтобы последний был отсоединен
  • мы освобождаем tmp
  • то мы переходим к новому следующему элементу и продолжаем

Вы изменили код для своей функции deletee , но он по-прежнему неверен:

 void deletee(ll *l) { node *k = l->head; while (k != NULL && k->next != NULL) { node *tmp = k->next->next; k = tmp; } } 

Вы вообще не изменяете этот список.

Вот решение с указателем на указатель, чтобы избежать особых случаев пустого списка и первого узла в списке. k указывает на ссылку, которая должна быть обновлена ​​при удалении узла, после каждого удаления проталкивается мимо сохраненного узла, кроме как в конце списка:

 void deletee(ll *l) { node **k = &l->head; while (*k != NULL) { /* delete the node */ node *tmp = *k; *k = (*k)->next; free(tmp); if (*k != NULL) { /* skip the preserved node */ k = &(*k)->next; } } }