Проверка, является ли указатель NULL, дает ошибку сегментации

Question

Постановка задачи: мы должны удалить каждый альтернативный узел связанного списка.Например: Исходный список: 1-> 2-> 3-> 4-> 5 до: 1-> 3-> 5

полное описание задачи: https://practice.geeksforgeeks.org/problems/delete-alternate-nodes/1/?ref=self

Как вы можете видетьЭто проблема с функцией, поэтому я не пишу полный код (просто нужно завершить функцию).Вот код, который я пишу:

void deleteAlt(struct Node *head){
    // Code here
    struct Node *traverse=head,*alternate=head->next;

    if(alternate->next==NULL)
    {
        head->next=NULL;
        return;
    }

    while(traverse->next!=NULL && alternate->next!=NULL)
    {
        traverse->next = alternate->next;
        traverse = traverse->next;
        alternate = traverse->next;
        if((alternate->next)==NULL) //presence of this if statement causes segmentation fault
        {
            traverse->next=NULL;
        }
    }
}

Я столкнулся с похожими проблемами в стеке потока, но их код и цель были разными, например, не инициализировать указатель и не сравнивать его.Однако моя проблема в другом.

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

Answer 1

вы делаете

while(traverse->next!=NULL && alternate->next!=NULL)
  traverse->next = alternate->next;
  traverse = traverse->next;
  alternate = traverse->next;
  if((alternate->next)==NULL) //presence of this if statement causes segmentation fault

так на самом деле

while(traverse->next!=NULL && alternate->next!=NULL)
  traverse = alternate->next;
  alternate = traverse->next;
  if((alternate->next)==NULL) //presence of this if statement causes segmentation fault

так на самом деле

while(traverse->next!=NULL && alternate->next!=NULL)
  alternate = alternate->next->next;
  if((alternate->next)==NULL) //presence of this if statement causes segmentation fault

так на самом деле

while(traverse->next!=NULL && alternate->next!=NULL)
  if((alternate->next->next->next)==NULL) //presence of this if statement causes segmentation fault

когда alternate->next->next равен NULL (не проверяется , в то время как ) alternate->next->next->next вызывает ошибку сегментации

---

Решение:

void deleteAlt(struct Node * head)
{
  if (head != NULL) {
    while (head->next != NULL) {
      Node * d = head->next;

      head->next = head->next->next;
      free(d);
      head = head->next;
    }
  }
}

Полная программа для доказательства:

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

typedef struct Node {
  int v;
  struct Node * next;
} Node;

Node * make(int v, Node * n)
{
  Node * r = malloc(sizeof(Node));

  r->v = v;
  r->next = n;

  return r;
}

void pr(Node * l)
{
  while (l != NULL) {
    printf("%d ", l->v);
    l = l->next;
  }
  putchar('\n');
}

void deleteAlt(struct Node * head)
{
  if (head != NULL) {
    while (head->next != NULL) {
      Node * d = head->next;

      head->next = head->next->next;
      free(d);
      head = head->next;
    }
  }
}

int main()
{
  Node * l = make(1, make(2, make(3, make(4, make(5, NULL)))));

  pr(l);
  deleteAlt(l);
  pr(l);

  /* free rest of list */
  while (l != NULL) {
    Node * n = l->next;

    free(l);
    l = n;
  }
}

Компиляция и исполнение:

pi@raspberrypi:/tmp $ gcc -pedantc -Wextra l.c
pi@raspberrypi:/tmp $ ./a.out
1 2 3 4 5 
1 3 5 
pi@raspberrypi:/tmp $ 

Выполнение в valgrind для проверки доступа к памяти / утечек

pi@raspberrypi:/tmp $ valgrind ./a.out
==2479== Memcheck, a memory error detector
==2479== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2479== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2479== Command: ./a.out
==2479== 
1 2 3 4 5 
1 3 5 
==2479== 
==2479== HEAP SUMMARY:
==2479==     in use at exit: 0 bytes in 0 blocks
==2479==   total heap usage: 6 allocs, 6 frees, 1,064 bytes allocated
==2479== 
==2479== All heap blocks were freed -- no leaks are possible
==2479== 
==2479== For counts of detected and suppressed errors, rerun with: -v
==2479== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)

---

(правка) В случае, если длина списка может быть даже, определение должно быть изменено на:

void deleteAlt(struct Node * head)
{
  while ((head != NULL) && (head->next != NULL)) {
    Node * d = head->next;

    head->next = head->next->next;
    free(d);
    head = head->next;
  }
}

изменение main для проверки:

int main()
{
  {
    Node * l = make(1, make(2, make(3, make(4, make(5, NULL)))));

    pr(l);
    deleteAlt(l);
    pr(l);

    /* free rest of list */
    while (l != NULL) {
      Node * n = l->next;

      free(l);
      l = n;
    }
  }
  {
    Node * l = make(1, make(2, make(3, make(4, NULL))));

    pr(l);
    deleteAlt(l);
    pr(l);

    /* free rest of list */
    while (l != NULL) {
      Node * n = l->next;

      free(l);
      l = n;
    }
  }
}

Компиляция и исполнение:

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra l.c
pi@raspberrypi:/tmp $ ./a.out
1 2 3 4 5 
1 3 5 
1 2 3 4 
1 3 

и valgrind :

pi@raspberrypi:/tmp $ valgrind ./a.out
==3450== Memcheck, a memory error detector
==3450== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3450== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3450== Command: ./a.out
==3450== 
1 2 3 4 5 
1 3 5 
1 2 3 4 
1 3 
==3450== 
==3450== HEAP SUMMARY:
==3450==     in use at exit: 0 bytes in 0 blocks
==3450==   total heap usage: 10 allocs, 10 frees, 1,096 bytes allocated
==3450== 
==3450== All heap blocks were freed -- no leaks are possible
==3450== 
==3450== For counts of detected and suppressed errors, rerun with: -v
==3450== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)

Answer 2

попробуйте это:

void deleteAlt(struct Node *head){

    struct Node * head_tmp=head;
    struct Node * tmp=NULL;

    while(head_tmp->next!=NULL){

        tmp=head_tmp->next;

        head_tmp->next=tmp->next;

        head_tmp=tmp->next;

        //do something for freeing tmp node 

    }


}

Answer 3

Я вижу запах кода в

if(alternate->next==NULL)
    {
        head->next=NULL;
        return;
    }

Что если у меня есть один узел? В этом случае alternate указывает на ноль.