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

}

• Michael K: What, no recursion? ;)

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