Thread: help with reversing something in a linklist

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

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.

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.

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.

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.

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.