How to Reverse singly linked list properly in C?

Question

well im starting with C and i've been asked to do a linked list that has random integers in its nodes data, they must be in ascendant order and later i have to reverse their order with a function. The problem im having is that in my reverse output, im only getting the first number and its not even reversed.

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

int N;

typedef struct node{
int num;
struct node *next;
}nodes;

int first_node(nodes *head){
if(head == NULL){
    printf("Error");
}
  else{
    head -> num= rand();
    head->next=NULL;
    }
}

int second_node(nodes *head){
nodes *uno=malloc(sizeof(nodes));
if(uno == NULL){
    printf("Error");

}

else{
    uno->num = rand();
    uno->next = NULL;
            if( uno->num>head->num){
               head->next=uno;

            }
            else{
                head= uno->next;
            }

}

}

int insert_node(nodes *head){
    nodes *dos=malloc(sizeof(nodes));
    if(dos == NULL){
        printf("Error");

    }

    else{
        dos->num = rand();
        dos->next = NULL;


        nodes *current = head;
        while(current!= NULL){
                if(current->num<dos->num && current->next==NULL){
                    current->next = dos;
                    return;

                }

                else if (current->num<dos->num && current->next->num>dos->num){
                dos->next=current->next;
                current->next=dos;
                return;

                }
                else if(head->num>dos->num){
                dos->next=head;
                head=dos;

        }
        current=current->next;

    }

}}

void printnodes(nodes *head){
    nodes *current = head;
    while (current != NULL){
        printf("%d\n",current->num);
        current = current ->next;
    }


}



void reverse(nodes *head)
{
 nodes *a=head->next;
 if(a!=NULL)
 {
   nodes *b=a->next;
   a->next=head;
   head->next=NULL;
   head=a;
   if(b!=NULL)
   {
     while(b!=NULL)
     {
      a=b;
      b=b->next;
      a->next=head;
      head=a;
     }
     a->next=head;
     head=a;
   }

   }
 }

int main(){
printf("Insert the number of nodes u want to create:");
scanf("%d", &N );
nodes *head =malloc(sizeof(nodes));
int i =3;

if(N==1){
    first_node(head);
}
else if (N ==2){
    first_node(head);
    second_node(head);

}
else if (N>2){

    first_node(head);
    second_node(head);
           while(i<=N){
            insert_node(head);
            i++;
           }
}


printnodes(head);
printf("\n\n Reversed \n\n");

reverse(head);
printnodes(head);


return 0;


}

The output im getting creating 5 nodes is : In order: 41 3445 3890 8709 16777

Reversed : 41

how can i fix this?, thanks and sorry for the bad english

This code does not compile. Can you post the necessary code to reproduce the problem? — PC Luddite, Oct 13 '15 at 04:50

score 0 · Answer 1 · answered Oct 13 '15 at 04:58

There are two very obvious problems in your code:

The first is that you assign to a local variable, expecting that assignment to be reflected once the function returns. I'm talking about your assignment to head in most functions. The problem here is that when you pass an argument to a function. it's passed by value, meaning it's copied and what you have in the function you call is just a copy or the original value. And as you should know, changing a copy will not change the original.

The second problem that I see at a quick glance is in the second_node function, where you first do

uno->next = NULL;

and potentially followed by

head= uno->next;

This will assign NULL to head.

The first problem is easy to solve, by emulating something called pass by reference. I say emulating, as C only have pass by value. You can emulate pass by reference in C using pointer, which means that to pass a pointer "by reference" in C, you have to pass a pointer to the pointer, like

int second_node(nodes **head){
    ...
}

You then call it using the address-of operator:

second_node(&head);

Then in second_node you use the dereference operator * to access the "original" head pointer, like

*head = uno->next;

Writing the above I noticed a third problem, and that is that you declare some functions as returning an int, but you don't actually return anything from the functions. Thankfully it seems that you don't use the returned value anywhere, but it's still is undefined behavior to not return a value in a function that should return a value. If you should not return a value from a function it must be declared as returning void:

void second_node(nodes **head){...}

How to Reverse singly linked list properly in C?

1 Answers1