help with reversing something in a linklist

This is a discussion on help with reversing something in a linklist within the C Programming forums, part of the General Programming Boards category; I'm trying to reverse something in a linklist but it doesn't seem to be working. Only the first element is ...

  1. #1
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335

    help with reversing something in a linklist

    I'm trying to reverse something in a linklist but it doesn't seem to be working. Only the first element is printed. I know the link list works because i have a simliar print method which traverses through the linklist and prints everything out. Any ideas?

    Code:
       custNode *previous = NULL;
       while (current != NULL)
       {
          custNode *tmp = current->next;
          current->next = previous;
          previous = current;
          current = tmp;
       }
       return previous;

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Sure, I've got a great idea. Stop using single linked lists, and use a double. Then come back and thank me.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    A double? Not such a great idea. Perhaps for one value or two values that are static where i wanted to swap them, but at the moment dynamic values are retrieved from a file.

    After further debugging, it seems after the reverse method is run and then when i attempt to print it there's only one element in the linked list. Before the reverse method is run everything is printed out fine
    Last edited by Axel; 10-19-2005 at 11:55 PM.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    A double linked list. Each node contains pointers to the previous and next nodes. They're much easier to manipulate.
    Code:
    struct node {
        struct node *prev, *next;
        ...stuff...
    };

    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Thanks for the hint although i want to be comfortable with Singly linked lists first.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Reverse a list:
    Code:
    for( temp = first node; temp; temp = temp2 )
    {
        temp2 = temp->next;
        temp->next = newlist head;
        newlist head = temp;
    }
    Lazy way to reverse-print a non-circular single linked list:
    Code:
    void printlist( struct node *ptr )
    {
        if( ptr )
        {
            printlist( ptr->next );
            printf("list pieces go here");
        }
    }

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    doesn't work either; i just get an endless loop... all the records are printed though, but they're still in order(un-reversed)

    Code:
    custNode *reverse(custNode *current)
    {
    
       custNode *temp2;
    
        for( custNodeNode *temp = current; temp; temp = temp2 )
        {
            temp2 = temp->next;
            temp->next = temp2;
            temp2 = temp;
        }
    
        return 0;
    
    }

  8. #8
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    and just to show, that my link list is working:

    Code:
    //there are 9 nodes which are retrieved from a text file
    
       custNode *temp2;
    
        for(  custNode *temp = current; temp; temp = temp2 )
        {
            temp2 = temp->next;
            printf("\nscanning list..");
        }
    
        return 0;
    produces:

    scanning list..
    scanning list..
    scanning list..
    scanning list..
    scanning list..
    scanning list..
    scanning list..
    scanning list..
    scanning list..

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Axel
    doesn't work either; i just get an endless loop... all the records are printed though, but they're still in order(un-reversed)

    Code:
    custNode *reverse(custNode *current)
    {
    
       custNode *temp2;
    
        for( custNodeNode *temp = current; temp; temp = temp2 )
        {
            temp2 = temp->next;
            temp->next = temp2;
            temp2 = temp;
        }
    
        return 0;
    
    }
    Why are you returning 0? You should be returning the newly ordered list.


    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Whoops..I've tried returning 'temp2', 'current' both give an endless loop.

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Notice one significant difference between your code and mine:
    Code:
    for( temp = first node; temp; temp = temp2 )
    {
        temp2 = temp->next;
        temp->next = newlist head;
        newlist head = temp;
    }
    Now yours:
    Code:
    custNode *reverse(custNode *current)
    {
    
       custNode *temp2;
    
        for( custNodeNode *temp = current; temp; temp = temp2 )
        {
            temp2 = temp->next;
            temp->next = temp2;
            temp2 = temp;
        }
    You need to try to understand the code, not just stick it in without knowing what it does.


    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Code:
      temp->next = temp2;
    hmm from what i understand, temp equals the first node in the list. The new head will be temp ->next which is the 2nd node (the new head).

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    1) Set up a new pointer to the next item in the list, so once we change the current node's next poitner, we don't lose our list.
    2) Make the current node's next pointer point at the top of the new list.
    3) Make the current node the top of the list.
    4) Use the node we set up in step 1 to advance down the list we're reversing.
    5) Repeat until done.

    Now use that to walk through my example.

    Quzah.
    Hope is the first step on the road to disappointment.

  14. #14
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    hmm i'm still having trouble figuring out what


    this should equal to = temp;

    for example if i have
    Code:
    [first node] city 1 
    [second node] city 2
    
           temp2 = temp->next; /* temp2 now equals to city 2 */
            temp->next = temp2; /* this just assigns city 2 to city 2 because temp->next is city 2 and temp 2 is city2 from the previous line*/
            ??? = temp; /* no idea what temp should equal to possibly current because we want the first element to equal to second one*/
    the following; has no effect, it just prints the ordered list.
    Code:
     temp2 = temp->next;
            temp->next = temp2;
            current->next = temp
    Last edited by Axel; 10-20-2005 at 02:15 AM.

  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You are in effect creating an entirely new list from the old one. This means you need something to hold onto it as you keep updating the new top of the list. So you need a seperate pointer to store that. When your function returns, you return that pointer.


    Quzah.
    Hope is the first step on the road to disappointment.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. reversing a string, again..
    By Disident in forum C Programming
    Replies: 5
    Last Post: 06-15-2009, 09:01 PM
  2. Reversing output in this function
    By rogster001 in forum C Programming
    Replies: 8
    Last Post: 02-07-2008, 06:36 AM
  3. LinkList Sorting in C
    By simly01 in forum C Programming
    Replies: 3
    Last Post: 11-25-2002, 01:21 PM
  4. MergeSort implementation with linklist.
    By Kam in forum C Programming
    Replies: 3
    Last Post: 10-21-2002, 12:04 PM
  5. Quick LinkList Help!!adding at the End
    By simly01 in forum C++ Programming
    Replies: 13
    Last Post: 07-28-2002, 08:19 AM

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