Reversing the elements of a linked list

[wizard25]

Hi

I'm having trouble completing the function void list::displayReverse() which basically displays the elements in the linked list in reverse. I have tried every possible way but it just doesn't seem to work. The function is associated with the struct

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

Can someone assist me in this

Thanks.

[helios]

If you don't want to copy the list somewhere else, you'll need to add a pointer to the previous node to make the list doubly linked.

[ne555]

you could reversed it like a stack, without additional memory, in linear time.

[blackcoder41]

void reverse(node &n)
{
    if(n.next) reverse(*n.next);
    cout << n.data << '\t';
}

[wizard25]

No I can't add the (node &n) because I'm not allowed

[blackcoder41]

Well I don't know how you're list class looks like so that's what I did. Anyway that should give the idea, you're on your own now.

[helios]

No, wait. I was right. There's no way to do it without copying the list somewhere or making it doubly linked.

[wizard25]

ok so how would you do that using the void list::displayReverse() function

[m4ster r0shi]

helios wrote:

No, wait. I was right. There's no way to do it without copying the list somewhere or making it doubly linked.

Ha! You may scratch that too :P

All you have to do is take this -> 1->2->3->4->5->NULL
and turn it into this ------> NULL<-1<-2<-3<-4<-5
(i.e. change the arrow direction)

#include <iostream>
using namespace std;

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

void print_list(Node * first)
{
    Node * cur=first;
    while (cur)
    {
        cout << cur->data << ' ';
        cur=cur->next;
    }
    cout << endl;
}

void reverse_list(Node * cur, Node * prev=0)
{
    if (cur->next) reverse_list(cur->next,cur);
    cur->next=prev;
}

int main()
{
    Node * n1=new Node; n1->data=1;
    Node * n2=n1->next=new Node; n2->data=2;
    Node * n3=n2->next=new Node; n3->data=3;
    Node * n4=n3->next=new Node; n4->data=4;
    Node * n5=n4->next=new Node; n5->data=5;

    n5->next=0;

    print_list(n1);
    reverse_list(n1);
    print_list(n5);

    delete n1;
    delete n2;
    delete n3;
    delete n4;
    delete n5;
}

EDIT:

See below for a better way.

[Duthomhas]

It is possible to do it in linear time without copying or recursion.
http://www.daniweb.com/code/snippet216991.html#post968991

@wizard25
This is one problem that you really must solve yourself. Hints only go so far here. The best one so far is that you must "change the arrow direction".

Example, given:

node0    node1--> node2

and considering node1, we want to change node1's pointer to go to node0 instead of node2.

node0 <--node1    node2

You will have to traverse the list and remember the previous node's address for each step in your loop. This means that at each step you must know: the previous node's address, this node's address, and the next node's address. Figure out how these three values relate to each other each time you go to the next node and you'll have figured it out. Be sure to use pencil and paper.

Good luck!