Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 186

# 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 << " ";
}
}
0
freedumb87
1 Solution

Commented:
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
0

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

}

}

call it initially like:

0

Associate Director - Product EngineeringCommented:
>> If you can print it in reverse you can store it in reverse.

That is the most correct comment posted on this page yet and I don't understand why you need to reverse it if you can actually access it in reverse order anyway.

However, assuming that you need to do so, here is a non-recursive implementation:

// assuming 'start' points to the first node

NodeType p, q, r ;
p = start ;
q = p -> next ;

while ( q != NULL )
{
r = q -> next ;
q -> next = p ;
p = q ;
q = r ;

} // end while

start = p ;

Hope that helps!

Mayank.
0

## Featured Post

Tackle projects and never again get stuck behind a technical roadblock.