检查指针是否为 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;
        }
    }
}

我在 stackoverflow 上遇到过类似的问题，但他们的代码和目标不同，比如不初始化指针并比较它。但是，我的问题有所不同。

在节点数为偶数的情况下，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时(不由while检查)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)