?
Solved

Reverse a list without making a tempList

Posted on 2003-03-27
3
Medium Priority
?
185 Views
Last Modified: 2010-04-01
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
Comment
Question by:freedumb87
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 
LVL 12

Expert Comment

by:Salte
ID: 8216487
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
 
LVL 10

Expert Comment

by:substand
ID: 8216517
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
 
LVL 30

Accepted Solution

by:
Mayank S earned 60 total points
ID: 8216706
>> 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

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question