help with reversing something in a linklist

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.

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.

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.

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;


}

Let's see how you're printing your list, and how you're calling it.


Quzah.

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

You should be doing:

Code:

newlist = reverset( start );
printList( newlist );

Quzah.

what does newlist refer to? I'm assuming the list.

Code:

custNode  *newList = reverse(start);
 printList(newList);

nothing is printed.

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.

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.

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.

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)

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

Ok, one more time, look at my origional example, which was correct, even while intoxicated:

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.

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

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;

}