asked on

Reverse a list without making a tempList

Is it possible to recursively reverse a list if you can't make a temp list? All I have access to is a pointer to the list. I can traverse the list and print it out in reverse but I can't seem to be able to actually store it in reverse order.
Here is how I print the list in reverse order. Can someone help me with the logic to actually change the data? Thanks.
void AuxPrintReverse(NodeType* myPtr, int i)
{
if(myPtr != NULL)
{
AuxPrintReverse(myPtr->next, i+1);
if( i == 10)
cout << endl;
cout << myPtr->info << " ";
}
}

Salte

If you can print it in reverse you can store it in reverse.

Without making a temporary list though is perhaps not quite true, you make so many recursive calls that the temporary list is stored in the stack frames of all those function instantiations :-)

But yeah, if we ignore that you really store the temporary list in such a way yes.

It is in fact easy to do also, I believe I have done enough hints...

I could show you how to reverse a list in LISP. This is done in exactly the manner which you are seeking but I think that would be too much of a spoiler.

How do you reverse an empty list?

How do you reverse a list with n+1 elements?

Alf

substand

you could do something like:

void ReverseLinkedList(NodeType* nodeToReverse, NodeType* reverseTo, int totalNodesToReverse)
{

if (totalNodesToReverse > 0)
{
NodeType* nextNodeToReverse=nodeToReverse->next;
NodeType* reverseNextNodeTo=nodeToReverse;

nodeToReverse->next=reverseTo;
totalNodesToReverse--

ReverseLinkedList(nextNodeToReverse, reverseNextNodeTo, totalNodesToReverse);
}

}

call it initially like:

ReverseLinkedList(myPtr, NULL, 10);

ASKER CERTIFIED SOLUTION

Mayank S

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial