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; Originally Posted by quzah 1) Set up a new pointer to the next item in the list, so once we ...

  1. #16
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Quote Originally Posted by quzah
    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.
    temp2 = temp->next;

    done.

    Quote Originally Posted by quzah
    4) Use the node we set up in step 1 to advance down the list we're reversing.
    temp = temp2;

    using the node created in step 1.

    Code:
    
    custNode *reverse(custNode *current)
    {
    
        custNode *temp2;
    
        for( custNode *temp = current; temp; temp = temp2 )
        {
            temp2 = temp->next;
            temp->next = temp2;
            temp = temp2; // updated line
        }
        return temp2;
    
    }

    So you need a seperate pointer to store that.
    done, temp2 the new reordered list is returned.
    The for loop is not running endlessly this time, but the list is still ordered..pfft.

  2. #17
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    No, it should be:
    Code:
            temp3 = temp2; // updated line
        }
        return temp3;
    }
    Otherwise, you aren't storing the top of the new list any place. Do this, take a deck of cards. Pretend it's your list. Now reverse the stack a card at a time. Where are you putting the cards when you reverse them? You have to set them someplace. Where you're setting them is your new list. The top card on the pile becomes the new lists's head.


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

  3. #18
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Hmm i see.

    ugh, this is so frustrating... i've modified the code to include the reordered list by creating another reference to the list as you said. But it's still ordered.

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

  4. #19
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Let's see how you're printing your list, and how you're calling it.


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

  5. #20
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Code:
    custNode *start = NULL;
    
    updateList(&start, cityName, xcoor, ycoor); // i have a while loop which scans the text file and gets each cityName xcoor etc.
    
    printList(start); <-- works fine.
    
     reverse(start); // run the reverse algorithm
    
      printList(start);  <--- same thing is printed after the reverse function is run

  6. #21
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You should be doing:
    Code:
    newlist = reverset( start );
    printList( newlist );

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

  7. #22
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    what does newlist refer to? I'm assuming the list.

    Code:
    custNode  *newList = reverse(start);
     printList(newList);
    nothing is printed.

  8. #23
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    i've managed to get it printed by sticking the printf statement inside the reverse function.

    Code:
    printf("\n%s", temp3->cityName)
    but

    city2
    (null)

    the last element in the list is null?

    and also

    Code:
    custNode  *newList = reverse(start);
     printList(newList);
    gives me a segmentation fault.

  9. #24
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    I've also tried it on 5 link list elements it reverses some but as usual the last element is null for some reason. This shouldn't be too hard to do, i still don't get why the last element is null.

  10. #25
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Try changing this:
    Code:
    temp->next = temp2;
    To this:
    Code:
    temp->next = temp3;
    And set temp3 to NULL at the beginning of your program.


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

  11. #26
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Code:
        charNode *temp2 ;
        charNode *temp3 = NULL;
    
        for( charNode *temp =  current; temp; temp = temp2 )
        {
          temp2 = temp->next;
            temp->next = temp3;
            temp = temp2; // updated line
    
            printf("\n%s", temp3->cityName);
    
        }
    hmm :|

    (null)
    (null)
    (null)
    (null)

  12. #27
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    to make things a little clear:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct charRecord
    {
       char numberone;
       char numbertwo;
       struct charRecord *next;
    };
    
    typedef struct charRecord charNode;
    
    void addElement(charNode **start, char numberone, char numbertwo);
    void printList(charNode *start);
    charNode* newNode(double numberone, double numbertwo);
    charNode* getString(charNode *start);
    charNode* reverse(charNode *start);
    
    int main()
    {
       charNode *start = NULL;
       start = getString(start);
       //reverse(start);
       printList(start);
       printf("\n +--+ reversing... +--+ \n");
       start = reverse(start);
       //printList(start);
       return 0;
    }
    
    
    charNode* getString(charNode *start)
    {
    
         addElement(&start, 'A', 'A');
         addElement(&start, 'B', 'B');
         addElement(&start, 'C', 'C');
    
         return start;
    
    
    }
    
    void addElement(charNode **start, char numberone, char numbertwo)
    {
    
       charNode *temp,*prev, *loc;
    
       temp = newNode(numberone, numbertwo);
    
    
       if (*start == NULL)
       {
          *start = temp;
       }
    
       else
       {
          loc = *start;
          prev = NULL;
    
          while (loc != NULL)
          {
             prev = loc;
             loc = loc->next;
          }
    
    
          temp->next = loc;
          if (prev == NULL)
          {
             *start = temp;
          }
          else
          {
             prev->next = temp;
          }
       }
    
    
    }
    
    
    charNode* newNode(double numberone, double numbertwo)
    {
    
       charNode *temp;
    
       temp = (charNode *) malloc(sizeof(charNode));
       if (temp == NULL)
       {
          printf("WARNING - Memory allocation error\n");
          exit(EXIT_FAILURE);
       }
    
    
       temp->numberone = numberone;
       temp->numbertwo = numbertwo;
    
    
       temp->next = NULL;
    
       return temp;
    }
    
    
    void printList(charNode *start)
    {
    
       while (start != NULL )
       {
    
          printf("\n%c %c\n", start->numberone, start->numbertwo);
          /*if (start->next != NULL)
          {
             printf("%s %.2f %.2f %s", "next element is -+> ", start->next->numberone, start->next->numbertwo, "**OK**");
          }*/
          start = start->next;
    
       }
    
    }
    
    charNode *reverse(charNode *current)
    {
    
        charNode *temp2;
         charNode *temp3 = NULL;
    
        for( charNode *temp = current; temp; temp = temp2 )
        {
            temp2 = temp->next;
            temp->next = temp3;
            temp3 = temp2;
            printf("\n%c %c\n", temp3->numberone, temp3->numbertwo );
        }
    
        return temp2;
    
    }
    
    /*
    
    A A
    
    B B
    
    C C
    
     +--+ reversing... +--+
    
    B B
    
    C C
    
    */
    
    should be:
    
    BB
    AA
    CC

  13. #28
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Ok, one more time, look at my origional example, which was correct, even while intoxicated:
    Quote Originally Posted by quzah
    Reverse a list:
    Code:
    for( temp = first node; temp; temp = temp2 )
    {
        temp2 = temp->next;
        temp->next = newlist head;
        newlist head = temp;
    }
    Simply replace 'newlist head' with temp3, which you've set to NULL at the start of the program, and return 'temp3' when you're done.


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

  14. #29
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    yeah that's what i've done:

    Code:
    harNode *reverse(charNode *current)
    {
    
        charNode *temp2;
         charNode *temp3 = NULL;
    
        for( charNode *temp =  current; temp; temp = temp2 )
        {
            temp2 = temp->next;
            temp->next = temp3;
            temp3 = temp;
            printf("\n%c%c\n", temp3->numberone, temp3->numbertwo);
        }
    
        return temp3;
    
    }
    still's still in the same order though:

    +--+ r

    AA

    BB

    CC

  15. #30
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    and also the following works but it gives me a segmentation fault at the last element:

    Code:
    charNode *reverse(charNode *current)
    {
    
        charNode *temp2;
         charNode *temp3 = NULL;
    
        for( charNode *temp =  current; temp; temp = temp2 )
        {
            temp2 = temp->next;
            temp->next = temp3;
            temp3 = temp2;
            printf("\n%c%c\n", temp3->numberone, temp3->numbertwo);
        }
    
        return temp3;
    
    }

Page 2 of 3 FirstFirst 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