Run time error while reversing a link list in C

Question

I am creating a simple linklist of integers and then reversing it. While reversing, last integer in original list is not getting printed. Instead a garbage value is printed. Here is the code:

#include<stdio.h>
#include<stdlib.h>
struct list
{
    int node;
    struct list *next; 
};

void insert(struct list **, int);
void print(struct list *);

int main()
{
    struct list *mylist= NULL, *tmp = NULL;

    insert(&mylist, 10);

    tmp = mylist;
    insert(&mylist, 20);
    insert(&mylist, 30);
    insert(&mylist, 40);
    insert(&mylist, 50);
    insert(&mylist, 60);
    insert(&mylist, 70);
    mylist=tmp;
    reverse(&mylist);
    printf("hello  ");
    print(mylist);

    return 0;
}

void reverse(struct list **temp)
{
    struct list **pre, **aft, **head;
    *pre = NULL;
    *head = *temp;
    if(*head == NULL )
        {
        return;
        }
    else
    {
        while((*head)!= NULL)
        {

        *aft =(*head)->next;

        (*head)->next = *pre;
        *pre = *head;
        *head = (*aft);
         printf("%d\t",(*pre)->node);
        }

    *temp = *pre;         
    }           
    }

void print(struct list *head)
{
    if(head==NULL)
        return;
    else
    {
            while(head!=NULL)
            {
             printf("%d\t",head->node);
             head=head->next;       
        }
    }
}


void insert(struct list **head, int value)
{   
    struct list *new_node;
    new_node = (struct list *)malloc(sizeof(struct list));

//node Creation
    new_node->node=value;
    new_node->next=NULL;

//Adding Node to list
    if(*head==NULL)
    {
        *head=new_node;  

    }
    else
    {
        while((*head)->next!=NULL)
        {   
            *head=(*head)->next;

        }
        (*head)->next=new_node;

    }

}

Output: 10 20 30 40 50 60 6532425 hello 6532425 60 50 40 30 20 10

Why?

Answer 1

First, your dereferencing and writing to indeterminate locations by doing this:

struct list **pre, **aft, **head;
*pre = NULL;    // <=== HERE
*head = *temp;  // <=== HERE

Neither of those pointers are initialized to anything, and are therefore indeterminate. dereferencing them for reading, writing, or even evaluating the pointer value itself is undefined behavior.

Fixing that is easy enough, since this function should not need any pointer-to-pointer variables except the passed in head pointer (which it must have by-address to reset the new list head once it is reversed).

void reverse(struct list **head)
{
    struct list *back = NULL, *cur = *head, *fwd = NULL;
    while (cur && cur->next)
    {
        fwd = cur->next;
        cur->next = back;
        back = cur;
        cur = fwd;
    }

    if (cur)
        cur->next = back;

    *head = cur;
}

That said, evidence suggests your work with pointers-to-pointers needs some more practice. There are additional errors, noted below

---

Memory leak in insert()

In your insert() function:

while((*head)->next!=NULL)
{
    *head=(*head)->next;

}
(*head)->next=new_node;

This code blindly overwrites the passed-in head pointer by-address, and in the process leaks any previously allocated nodes except the the last-one-added. If you're going to receive a double pointer and use it for walking the list to find the location of the new insertion, do so correctly. The pointer-game being played with tmp in main() should not be necessary, and with the following implementation, it isn't:

void insert(struct list **head, int value)
{
    // find the address of the last `next` pointer in
    // the list. note: it may be the head pointer itself
    while (*head)
        head = &(*head)->next; 

    *head = malloc(sizeof(**head));
    (*head)->node = value;
    (*head)->next = NULL;
}

---

Simplify print()

A minor inconvenience in your print() code is also present. There is no need for the initial check for the passed in pointer as NULL. Just use the break-condition of the while loop:

void print(struct list *head)
{
    while(head)
    {
        printf("%d ",head->node);
        head=head->next;
    }
    printf("\n");
}

---

Putting It All Together

Using the above implementations, and the following main():

int main()
{
    struct list *mylist = NULL;

    insert(&mylist, 10);
    insert(&mylist, 20);
    insert(&mylist, 30);
    insert(&mylist, 40);
    insert(&mylist, 50);
    insert(&mylist, 60);
    insert(&mylist, 70);

    print(mylist);
    reverse(&mylist);
    print(mylist);

    return 0;
}

Output

10 20 30 40 50 60 70 
70 60 50 40 30 20 10 

Answer 2

The problem is in this declaration:

struct list **pre, **aft, **head;

So, they are pointers to a pointer to a list, and then, you do things like this:

*pre = NULL;

The problem is that pre has not been initialized, so it holds garbage at this point. You are basically setting a random address in memory to NULL. You have two options: allocate space for them (with malloc and free afterwards), or change them to be like this:

struct list *pre, *aft, *head;

That way, they can be assigned safely. Your function would be modified like this:

void reverse(struct list **temp) {
    struct list *pre, *aft, *head;
    pre = NULL;
    head = *temp;
    if(head == NULL ) {
        return;
    } else {
        while(head!= NULL) {
            aft =head->next;
            head->next = pre;
            pre = head;
            head = aft;
            printf("%d\t",pre->node);
        }
        *temp = pre;
    }
}

Doing that, I get the following output:

10      20      30      40      50      60      70      hello  70       60
50      40      30      20      10

EDIT:

I've also noticed that you are changing the value of head inside the functions insert and print. I recommend using a temporal variable instead to iterate the list. That also frees you from that trick you were using in main with tmp.

Anyway, the complete code modified can be seen here. If yours is still giving you trouble, post an update or Ideone link with the modified code that still fails.