reversing a singly linked list

This is a discussion on reversing a singly linked list within the C Programming forums, part of the General Programming Boards category; i'll be very thankful if u can help me out here ...i have to write a program in c language ...

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    63

    reversing a singly linked list

    i'll be very thankful if u can help me out here ...i have to write a program in c language ...to REVERSE A LINKED LIST.i have tried it until the point where the reversal is not used coz i don't know the logic which will be used to reverse a linked list....for example if a list is there like: 0->1->2->3->4->5->6
    then the reverse of linked list would be 6->5->4->3->2->1->0.
    i have tried it partially though...plz help me out and i'll be very greatful to u if u can help me in the reversing code....i've done something like this...
    Code:
    #include<stdio.h>
    #include<conio.h>
    struct link
    {
    int data;
    struct link*ptr;
    };
    typedef struct link node;
    int main()
    {
    int i,size;
    node*start,*temp,*p,*last;
    clrscr();
    printf("enter the size of list");
    scanf("%d",&size);
    start=NULL;
    for(i=0;i<size;i++)
    {
     if(start==NULL)
       {
           start=(node*)malloc(sizeof(node));
           printf("enter the elements of list\n");
           scanf("%d",&start->data);
           start->ptr=NULL;
       }
      else
        {
      for(p=start;p->ptr!=NULL;p=p->ptr)
      temp=(node*)malloc(sizeof(node));
      scanf("%d",&temp->data);
      p->ptr=temp;
      temp->ptr=NULL;
        }
    }
    //now what do i do?after this?here the reverse of a linked list is to be done.....plz help me here..

  2. #2
    Registered User
    Join Date
    Feb 2005
    Posts
    12
    You are a gem galmca. Your persistence with your indentation style is rock solid, nobody can move you. As you can make out I'm n00b to this forum and was going through the previous posts and found one of your posts locked. God knows, whom will you listen to!

  3. #3
    Registered User
    Join Date
    Nov 2004
    Location
    India
    Posts
    515
    Ah, dont worry much about galmca, galmca and cgod are our resident demons. nobody minds them..

    btw galmca, for reversing, you would have to use recursions..

    something like

    Code:
     void reverse(void *startaddr)
     { 
        if(startaddr->next==NULL )
         {
           // print the data in the node
         }
        reverse(startaddr->next)
         // print the data in the node
    }
    and please please please indent that code of yours
    Last edited by PING; 02-07-2005 at 08:41 AM.
    Code:
    >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

  4. #4
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    You shouldn't have to use recursion. It seems simple enough. Pseudo-code follows:
    Code:
    set a temp pointer to the head of the list
    set a back pointer to NULL
    while the temp pointer is not at the end of the list
    {
       store a next pointer to the next node
       set temp pointer's next to the back pointer
       set the back pointer to this node
       set the temp pointer to the next pointer
    }
    head of the list = back pointer
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  5. #5
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Theres only one problem: This is a single direction link list as indicated by his title. The only way to reverse a single direction link list is to basically build another list. This is why the majority of lists are two directional link lists, so you can go forward and backwards.

  6. #6
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    For the benefit of the OP, I wasn't going to actually write any code, but I want to make sure I'm thinking correctly. Please excuse any syntax errors; this is still meant as pseudo-code.
    Code:
    struct node
    {
       int data;
       node *next;
    };
    
    node* reverse(node* head)
    {
       node *temp, *back, *next;
       for(temp = head, back = NULL; temp != NULL; temp = next)
       {
          next = temp->next;
          temp->next = back;
          back = temp;
       }
       return back;
    }
    On a list with 2 nodes:
    Code:
    Head of List: Node 1
    Node 1 (next:Node 2)
    Node 2 (next:NULL)
    
    Call reverse(Node 1)
    
    In reverse:
    temp = Node 1
    back = NULL
    while (temp != NULL)
       next = Node 2
       Node 1 -> next = NULL
       back = Node 1
       temp = Node 2
    while (temp != NULL)
       next = NULL
       Node 2 -> next = Node 1
       back = Node 2
       temp = NULL
    return Node 2
    
    Reversed list:
    Head of List: Node 2
    Node 1 (next:NULL)
    Node 2 (next:Node 1)
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  7. #7
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,175
    You definitely don't need recursion:
    Code:
    itsme@dreams:~/C$ cat revllist.c
    #include <stdio.h>
    #include <malloc.h>
    
    typedef struct node_s
    {
      int num;
      struct node_s *next;
    } NODE;
    
    void show_list(NODE *list)
    {
      while(list)
      {
        printf("%d ", list->num);
        list = list->next;
      }
      putchar('\n');
    }
    
    int main(void)
    {
      NODE *list = NULL, *temp = NULL, *n;
      int i;
    
      for(i = 0;i < 5;++i)
      {
        if(!(n = malloc(sizeof(NODE))))
        {
          puts("Memory allocation error!");
          return 1;
        }
        n->num = i + 1;
        n->next = list;
        list = n;
      }
    
      printf("Original List: ");
      show_list(list);
    
      while(list)
      {
        n = list->next;
        list->next = temp;
        temp = list;
        list = n;
      }
      list = temp;
    
      printf("Reversed List: ");
      show_list(list);
    
      while(list)
      {
        n = list->next;
        free(list);
        list = n;
      }
    
      return 0;
    }
    Code:
    itsme@dreams:~/C$ ./revllist
    Original List: 5 4 3 2 1
    Reversed List: 1 2 3 4 5
    Last edited by itsme86; 02-07-2005 at 10:30 AM.
    If you understand what you're doing, you're not learning anything.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 11:01 AM
  2. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 02:48 PM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 06:46 PM
  4. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 02:27 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21