Я пытался создать функцию на 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 сохраняет следующее значение для последующего удаления 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; } } }