4
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$
#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;
}

}

\$\endgroup\$
  • \$\begingroup\$ What, no recursion? ;) \$\endgroup\$ – Michael K Jun 20 '11 at 19:11
3
\$\begingroup\$

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;

}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.