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
  • Last Modified:

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
Asked:
freedumb87
1 Solution
 
SalteCommented:
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
 
substandCommented:
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);
0
 
Mayank SAssociate 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

[Webinar] Database Backup and Recovery

Does your company store data on premises, off site, in the cloud, or a combination of these? If you answered “yes”, you need a data backup recovery plan that fits each and every platform. Watch now as as Percona teaches us how to build agile data backup recovery plan.

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