Checking if pointer is NULL gives segmentation fault

Question

The problem statement: We have to delete every alternate node of a Linked List. Eg: Original list: 1->2->3->4->5 to: 1->3->5

complete problem statement: https://practice.geeksforgeeks.org/problems/delete-alternate-nodes/1/?ref=self

As you can see, this is a function problem so I'm not actually writing the complete code(just have to complete the function). Here is the code that I'm writing:

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

I have gone through similar problems on stackoverflow but their code and objective were different, like, not initializing the pointer and comparing it. However, my problem is different.

In the case when number of nodes is even, alternate is always going to be NULL and hence there should be no initialization problem.

@songziming in that case traverse->next will be NULL and nothing happens(because it does not enter the while loop). Which is the expected behavior. — Breakpoint
– Breakpoint, Commented Mar 6, 2019 at 6:20
traverse->next will be NULL, which means alternative will be NULL. Now you see the problem? — Ziming Song
– Ziming Song, Commented Mar 6, 2019 at 6:22
@TotallyNoob look at my answer, I did transformations step by step from your code to show the problem — bruno
– bruno, Commented Mar 6, 2019 at 6:29

bruno · Accepted Answer · 2019-03-06 07:25:50Z

you do

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

so in fact

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

so in fact

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

so in fact

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

when alternate->next->next is NULL (not checked by the while) alternate->next->next->next causes your segmentation fault

A solution is :

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

A complete program to prove :

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

Compilation and execution:

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

Execution under valgrind to check memory accesses/leaks

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)

(edit) In case the length of the list can be even the definition must be changed to :

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

modifying main to check :

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

Compilation and execution :

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

and under 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)

Thanks Bruno. I kind of get what my mistake is but how can I resolve it? In case of even number of nodes I have to drop the last node which needs this condition evaluation.
@TotallyNoob I edited my answer to put a solution, including a full program to execute it and show it works
I can't thank you enough for the help but it still gives segmentation fault. I feel that this might be problem at their backend since the code works perfectly under valgrind
@TotallyNoob may be they also do test with a partial list having an even length ? I edited my answer to also manage that case

Android · Accepted Answer · 2019-03-06 06:45:27Z

0

try this:

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 

    }


}

edited Mar 6, 2019 at 6:45

Android

1,4344 gold badges16 silver badges24 bronze badges

answered Mar 6, 2019 at 6:31

Y.Jie

1522 silver badges10 bronze badges

Comments

madhu sudhan · Accepted Answer · 2019-03-06 06:20:21Z

-1

I can see a code smell in

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

What if i have a single node? In that case alternate points to null.

answered Mar 6, 2019 at 6:20

madhu sudhan

1772 silver badges14 bronze badges

3 Comments

Breakpoint Over a year ago

In that case traverse->next will be NULL and nothing happens(because it does not enter the while loop). Which is the expected behavior.

madhu sudhan Over a year ago

What if alternate is NULL? If alternate is NULL then in if condition, its NULL -> next . Hence segmentation fault

Breakpoint Over a year ago

You are talking about first if statement and I corrected that. Still segmentation fault. In the case of while loop it won't enter it.

Collectives™ on Stack Overflow

Checking if pointer is NULL gives segmentation fault

3 Answers 3

4 Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related