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;

---

Sure, I've got a great idea. Stop using single linked lists, and use a double. Then come back and thank me. :)


Quzah.

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 :confused:

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.

Thanks for the hint although i want to be comfortable with Singly linked lists first.

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.

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;

}

---

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..

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.

Whoops..I've tried returning 'temp2', 'current' both give an endless loop.

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.

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).

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.

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

---

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.

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;

}

---

Quote:

---

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:

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.

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;

}

---

Actually, it probably segfaults on the printf, where you dereference temp3. I think you should test if test3 is NULL before you dereference it.

Have you tried quzah's ??

Code:

---

for( temp = first node; temp; temp = temp2 )
{
    temp2 = temp->next;
    temp->next = newlist head;
    newlist head = temp;
}

---

*Edited

You have a big problem naming your variables. temp1, temp2, temp3. Confusing aint it??

Quote:

---

Originally Posted by loko

Have you tried quzah's ??

---

yes, his last suggestion was to set temp3 to null and change the newlist head's to temp3. This gives a print out of the nodes in their original order.

Quote:

---

Originally Posted by loko

Have you tried quzah's ??
You have a big problem naming your variables. temp1, temp2, temp3. Confusing aint it??

---

i only did that to keep inline with quzah's example and if i had any problems it'd be easier to explain.

Quote:

---

Actually, it probably segfaults on the printf, where you dereference temp3. I think you should test if test3 is NULL before you dereference it.

---

Code:

---



charNode *reverse(charNode *current)
{

    charNode *temp2;
    charNode *temp3 = NULL;

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

    return temp3;

}

---

segmentation fault without printing nothing

Why did you put the if check in there? That's not right. I give up.


Quzah.

i only did that because dwks said i should test if test3 is NULL before i dereference it.

Code:

---

if( foo )
{
}
printf( do something with foo no matter what, becaue this is outside the if )

---

See, it doesn't do any good to test it if you're going to just print it anyway.


Quzah.

indeed. Sorry i forgot to mention, I actually did try placing the printf statement inside the if statement but as usual it gives me a segmentation fault at the last element.

+--+ reversing... +--+

BB

CC

abnormal program termination: segmentation fault

Well I don't know how you can possibly be screwing it up this bad. I can't explain it any more. I'm right. My code is right. You're just messing it up some how. There's no way this should be that hard. My first example was 100% correct.

Code:

---

#include<stdio.h>
#include<stdlib.h>

struct node
{
    struct node *next;
    int data;
};

void printlist( struct node * );
struct node *revlist( struct node * );

int main( void )
{
    struct node *list = NULL, *newnode;
    int x;
   
    for( x = 0; x < 10; x++ )
    {
        newnode = malloc( sizeof( *newnode ) );
        if( newnode == NULL )
        {
            printf("So sad.\n");
            exit( 0 );
        }
   
        newnode->next = list;
        newnode->data = x;
        list = newnode;
    }
    printlist( list );
   
    list = revlist( list );
    printlist( list );
   
    for( ; list; list = newnode )
    {
        newnode = list->next;
        free( list );
    }
   
    return 0;
}

void printlist( struct node *n )
{
    for( ; n; n = n->next )
    {
        printf( "data is %d\n", n->data );
    }
}

struct node *revlist( struct node *n )
{
    struct node *temp = NULL, *temp2 = NULL, *temp3 = NULL;
   
    for( temp = n; temp; temp = temp2 )
    {
        temp2 = temp->next;
        temp->next = temp3;
        temp3 = temp;
    }
    return temp3;
}

---

[edit]
It doesn't really matter though. If you can't wrap your head around the code, having it doesn't do you any good.
[/edit]

Quzah.

the problem was:

Code:

---


revlist(list);

---

i wasn't saving what was happening in "start" (in main)

i changed it to start = revlist(list);

works now, thanks.

another problem was:

Code:

---

    printf( "%c %c\n", temp3->numberone, temp3->numbertwo );

---

i was attempting to print inside the reverse method, the new fully reversed list wasn't being saved. Instead, an incomplete one was printed.

Quote:

---

Originally Posted by Axel

the problem was:

Code:

---


revlist(list);

---

i wasn't saving what was happening in "start" (in main)

i changed it to start = revlist(list);

works now, thanks.

---

You mean sort of like what I already told you to do?

Quote:

---

Originally Posted by quzah

You should be doing:

Code:

---

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

---

Quzah.

---

:rolleyes:


Quzah.

Quote:

---

Originally Posted by quzah

Code:

---

if( foo )
{
}
printf( do something with foo no matter what, becaue this is outside the if )

---

See, it doesn't do any good to test it if you're going to just print it anyway.


Quzah.

---

Thats the same thing i was telling him in the other threads he made. He thinks that becoz something isnt printing correctly that something is wrong. Well he was printing somthing that is not even related to what he was doing that.

This thread will just go on and on.

loko, in most cases, when something isn't printed somewhere, i.e. if you stick a printf statement inside a while loop and it's not printing it gives you an idea that the while is evaluating to false and its a great indication that something you assumed in your code was wrong.

Another example is if in an array element X in an array is empty or has the wrong character than you expected, then a printf statement can be quiet handy to debug it and to understand what's actually inside the array.

I may of not been clear with how i explained the problem; sorry about that.

printf is good for testing things in your code. Correct, but thats if you put it in the right place. If you look at quzah's code its a small peice of code and its obvious that itll work. Your printf didnt do its job to tell you if the code works or not.

In your reversing function you dont print the result until the function is done. What your doing is your printing while its reversing. And when you dont get a reverse order in your printing, you say its not working.

What about try to print only when the reversing is done?? Maybe youll get a reverse order?