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

Question

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

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

#include <stdio.h> 
#include <stdlib.h> 

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; 
} 

Answer 1

Нам нужно обновить и 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);:

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

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

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

Answer 2

в этом коде твоего:

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
• то перейти к новому следующему элементу и продолжить

Answer 3

Вы изменили код для 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; 
     } 
    } 
}