Creating and reversing a linked list

Question

Here is my program which creates a linked list and reverses it:

#include<stdio.h>
#include<stdlib.h>
struct node {
    int data;
    struct node *next;
};
struct node *list=NULL;
struct node *root=NULL;
static int count=0;
struct node *create_node(int);//function to create node
void travel_list(void);
void create_list(int);
void reverse_list(void);
int main()
{
    int i, j, choice;
    printf("Enter a number this will be root of tree\n");
    scanf("%d", &i);
    create_list(i);
    printf("Enter  1 to enter more numbers \n 0 to quit\n");
    scanf("%d", &choice);
    while (choice!=0){
     printf("Enter a no for link list\n");
        scanf("%d",&i);
//  printf("going to create list in while\n");
    create_list(i);
        travel_list(); 
    printf("Enter  1 to enter more numbers \n 0 to quit\n");
    scanf("%d", &choice);
    }
    printf("reversing list\n");
     reverse_list();
     travel_list();
 }


// end of function main
void create_list (int data)
{
 struct node *t1,*t2;
 //printf("in fucntion create_list\n");
 t1=create_node(data);
 t2=list;
 if( count!=0)
 {
   while(t2->next!=NULL)
   {
   t2=t2->next;
   }
 t2->next=t1;
 count++;
 }
 else 
  {
   root=t1;
   list=t1;
   count++;
  }
}
struct node *create_node(int data)
{
    struct node *temp;
    temp = (struct node *)malloc(sizeof(struct node));
        temp->data=data;
    temp->next=NULL;
  //      printf("create node temp->data=%d\n",temp->data);
//  printf("the adress of node created %p\n",temp);
    return temp;
}
void travel_list(void )
{
 struct node *t1;
 t1=list;
 printf("in travel list\n");
 while(t1!=NULL)
 {
 printf("%d-->",t1->data);
 t1=t1->next;
 }
 printf("\n");
}
void reverse_list(void)
{
    struct node *t1,*t2,*t3;
       t1=list;
    t2=list->next;
    t3=list->next->next; 
   int reverse=0;
   if(reverse==0)
   {
    t1->next=NULL;
    t2->next=t1;
    t1=t2;
    t2=t3;
    t3=t3->next;
    reverse++;

    }


    while(t3!=NULL)
     {

     t2->next=t1;
    t1=t2;
    t2=t3;
    list=t1;
    travel_list();
    t3=t3->next;
    }
    t2->next=t1;
    list=t2;
}

I am posting it for further review if there can be any improvements to the algorithm, etc.

Answer 1

#include<stdio.h>
#include<stdlib.h>
struct node {
    int data;
    struct node *next;
};
struct node *list=NULL;
struct node *root=NULL;
static int count=0;

Don't store data in global variables. It makes your code unreusable and harder to follow.

struct node *create_node(int);//function to create node
void travel_list(void);
void create_list(int);
void reverse_list(void);
int main()
{
    int i, j, choice;

Using variables like i and j only make sense if used in the sense of indexes. Otherwise, the code just gets harder to read. Choice is also not very informative.

    printf("Enter a number this will be root of tree\n");
    scanf("%d", &i);
    create_list(i);
    printf("Enter  1 to enter more numbers \n 0 to quit\n");
    scanf("%d", &choice);
    while (choice!=0){
     printf("Enter a no for link list\n");
        scanf("%d",&i);

Use consistent indentation. Otherwise things will go downhill fast.

//  printf("going to create list in while\n");

Don't leave dead code in your code, that's what source control is for.

    create_list(i);
        travel_list(); 
    printf("Enter  1 to enter more numbers \n 0 to quit\n");
    scanf("%d", &choice);

Deja vu. Why isn't the previous instance doing the same thing done in the loop?

    }
    printf("reversing list\n");
     reverse_list();
     travel_list();
 }


// end of function main
void create_list (int data)

This function appends to the end of a list, it doesn't create it. Use function names that indicate what is really happening.

{
 struct node *t1,*t2;

t1 and t2 are very uninformative variable names.

 //printf("in fucntion create_list\n");
 t1=create_node(data);
 t2=list;
 if( count!=0)

This is the only place that count is used. Check whether list is null instead.

 {
   while(t2->next!=NULL)
   {
   t2=t2->next;
   }
 t2->next=t1;
 count++;
 }
 else 
  {
   root=t1;

You don't ever seem to do anything with root.

   list=t1;
   count++;
  }
}
struct node *create_node(int data)
{
    struct node *temp;

The new node isn't really temporary

    temp = (struct node *)malloc(sizeof(struct node));
        temp->data=data;
    temp->next=NULL;
  //      printf("create node temp->data=%d\n",temp->data);
//  printf("the adress of node created %p\n",temp);
    return temp;
}
void travel_list(void )
{
 struct node *t1;
 t1=list;
 printf("in travel list\n");
 while(t1!=NULL)
 {
 printf("%d-->",t1->data);
 t1=t1->next;
 }
 printf("\n");
}
void reverse_list(void)
{
    struct node *t1,*t2,*t3;

This piece of code would be way easier to follow if you used real names

       t1=list;
    t2=list->next;
    t3=list->next->next; 

This is going to fail for lists shorter then three elements

   int reverse=0;
   if(reverse==0)

This will always be true since you just assigned reverse = 0.

   {
    t1->next=NULL;
    t2->next=t1;
    t1=t2;
    t2=t3;
    t3=t3->next;
    reverse++;

You never use reverse again

    }


    while(t3!=NULL)
     {

     t2->next=t1;
    t1=t2;
    t2=t3;
    list=t1;
    travel_list();
    t3=t3->next;
    }
    t2->next=t1;
    list=t2;
}

My version of reverse_list (untested)

struct node * reverse_list(struct node * list)
{
    struct node *previous, *current;
    previous = NULL;
    current = list;
    while(current)
    {
        struct node * next = current->next;
        current->next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

}

Answer 2

This is my version in C-language. I am reusing the root node instead of an extra node since it is manipulated with in the function and will not change globally. Also, look at the way I am returning the head, once the entire reversal of the list is complete. This is perfectly valid, the passing and returning of a struct by functions in C, and you can use it to get rid of global variables.

node *reverselinklist(node *root)
{
node *pre,*cur;
pre='\0';
while(root!='\0')
{
cur=root->next;
root->next=pre;
pre=root;
root=cur;

}
return pre;

}

Answer 3

You should compile with all warnings enabled, e.g. gcc -Wall:

review.c: In function ‘main’:
review.c:16: warning: unused variable ‘j’
review.c:34: warning: control reaches end of non-void function

This tells you that you have an unused variable and that main() is missing a return statement. You should fix these and any other warnings.

You should also pay attention to formatting your code.

Answer 4

here is LinkedList class I implemented using c++ templates. also I implemented reverse and sorting linked list by merge sort

template <class T>
void LinkedList<T>::reverseList()
{
  Node<T> *curr = head, *prev = head, *save = NULL;

  while (curr)
    {
      save = curr->next;
      curr->next = prev;
      prev = curr;
      curr = save;
    }

  head->next = NULL;
  head = prev;
}

https://code.google.com/p/medicine-cpp/source/browse/trunk/cpp/ds/LinkedList.cpp