Удалите каждый другой узел из связанного списка, заданного 1-> 2-> 3-> 4, чтобы получить 2-> 4?

Question

Я смотрел на других форумах, как удалять каждый другой узел, но они всегда получают результат 1-> 3, а я хочу 2-> 4. У меня проблемы с этим. Я потратил часы, глядя на это, и любая помощь будет оценена по достоинству. Я добавил несколько операторов printf, чтобы увидеть, где я ошибаюсь. Это выход я получаю:

17 3 8 8 20 13 15 17 10 13 


current: 17 
forward: 3 
free: 17 
current: 8 
forward->next: 8 
-------End------ 

free: 8 
current: 8 
forward->next: 20 
-------End------ 

free: 8 
current: 20 
forward->next: 13 
-------End------ 

free: 20 
current: 13 
forward->next: 15 
-------End------ 

free: 13 
current: 15 
forward->next: 17 
-------End------ 

free: 15 
current: 17 
forward->next: 10 
-------End------ 

free: 17 
current: 10 
forward->next: 13 
-------End------ 

free: 10 
current: 13 

Вот мой код:

node *deleteEveryOther(node *head) 
{ 
    node *forward, *current; 

    if (head == NULL) 
     return NULL; 

    current = head; 
    printf("\n\ncurrent: %d\n", current->data); 
    forward = head->next; 
    printf("forward: %d\n", forward->data); 

    while(current != NULL && forward != NULL) 
    { 
     printf("free: %d\n", current->data); 
     free(current); 

     current = forward->next; 
     printf("current: %d\n", current->data); 

     forward->next = current->next; 
     printf("forward->next: %d\n", forward->next->data); 
     //if(previous->next != NULL) 
      //previous = previous->next; 

     printf("-------End------\n\n"); 
    } 

    return head; 
} 

Здесь я редактировал (применяя алгоритм я видел) код немного:

узел * deleteEveryOther (узел * head) { узел * прежний, * текущий;

if (head == NULL) 
    return NULL; 

previous = head; 
current = head->next; 

free(previous); 
previous = current; 
current = head->next; 

while(current != NULL && previous != NULL) 
{ 
    previous->next = current->next; 

    free(current); 

    previous = previous->next; 

    if(previous != NULL) 
     current = previous->next; 

} 

return head; 

}

// ----------------- RECURSIVE ПОДХОД ----------------- ---------

void deleteEveryOtherRecursively(node *head)` 
{ 
    if (head == NULL) 
    return; 

    node *current = head; 

    if (current == NULL) 
     return; 

    node *forward = head->next; 
    head = current->next = forward->next; 

    free(current); 

    deleteEveryOtherRecursively(head); 
} 

Answer 1

Вы можете освободить первый узел и получить новую голову вне цикла while. Затем освободите все альтернативные узлы внутри цикла while.

Я немного изменил код.

struct node *deleteEveryOther(struct node *head) 
{ 
    struct node *forward, *current; 

    /* If empty list */ 
    if (head == NULL) 
      return NULL; 

    /* Free first element */ 
    current = head; 
    forward = head->next; 
    free(current); 

    /* Get new head */ 
    current = forward; 
    head = current; 

    /* Now remove all next elements */ 
    while (current != NULL) { 
      forward = current->next; 
      if (forward != NULL) { 
        current->next = forward->next; 
        free(forward); 
      } 
      current = current->next; 
    } 

    /* Return new head */ 
    return head; 
} 

В вашем коде имеется несколько ошибок. Например, вы не обновляете новый head, но возвращаете тот же старый head. Также вы разыменовали некоторые указатели, не проверяя, являются ли они NULL (в ваших заявлениях printf).

Это также можно сделать рекурсивно. В вашей версии вы не возвращаете голову (функция void), что является проблемой. Есть и другие проблемы. Вы можете сравнить код ниже с кодом и увидеть различия.

/* deleteEveryOtherRecursively: recursively delete odd numbered nodes */ 
struct node *deleteEveryOtherRecursively(struct node *head) 
{ 
    struct node *forward; 

    /* Base case */ 
    if (head == NULL) 
      return NULL; 

    forward = head->next; /* Get the next node in forward */ 
    free(head);   /* free old head */ 
    head = forward;  /* new head points to next elem */ 

    if (head != NULL)  /* recur down if needed */ 
      head->next = deleteEveryOtherRecursively(head->next); 

    return head;   /* return new head */ 
} 

Answer 2

Возможно, вы захотите удалить первый узел, а затем применить алгоритм к оставшемуся связанному списку. Это один из способов, которым он должен работать, и это самый простой, на мой взгляд.