void reverseList(nodePtr &theList)
{
// for each node in theList
if (theList->next != NULL)
{
reverseList(theList->next);

theList->next = theList; // store next pointer in the list
}
}

The function above is supposed to reverse a linked list so that it goes from back to front instead. I am required to use the "void reverseList(nodePtr &theList)" parameter list and cannot change it. The problem I am having is that at the end of recursion I am stuck at the end of the list and don't know how to get back to the new beginning of the list.

I dont think so.
theList->next = theList; //Pointing to its self.

Change to..
theList->next->next = theList;


Sure fire way to get a stack overflow when the linked list gets to big.. Anyway if you have to use the code then create a pointer that holds the end node , which after the reverse become the start. I think that you may also have to put a null at the end of the list as the new last node will point to the one above it.

How do I create a pointer within the function to hold the end node? Everything has to be in the function but the temporary pointer will keep being updated won't it?

Try this. This will return the pointer to the new start of the list.
nodePtr *reverseList(nodePtr &theList)
{
static nodePtr *lastNode = NULL;
if (theList->next != NULL)
{
reverseList(theList->next);

theList->next->next = theList;
}else
{
lastNode = theList;
}
return(lastNode);
}

Sorry blindman but the function must be a void (with only that one parameter)

Well you could make the lastNode pointer a global...
nodePtr *lastNode = NULL;
void reverseList(nodePtr &theList)
{
if (theList->next != NULL)
{
reverseList(theList->next);

theList->next->next = theList;
}else
{
lastNode = theList;
}
}


Should you not create a class Node with the method ReverseList and a property lastNode.

try this:

nodePtr *temp = theList->next;
theList->next = NULL;
temp->next = theList;

Ok, the problem is:

EVERYTHING must be done in the function. We are especially not allowed to use globals ever and he says it would be too easy to add a lastNode to a struct.

I saw some code on the net that does it fine - very ingenious actually and short too. I'm not sure how exactly it works - only 6 lines and very simple - so I have to figure that out.

Would you like me to post it?

void reverseList(nodePtr &theList)
{
if (theList->next != NULL)
reverseList(theList->next);
nodePtr *temp = theList->next;
theList->next = NULL;
temp->next = theList;
}
}

doesn't work?

no.. the last statement "temp->next=theList", cannot work since temp is a null value the first time that statement executes.

This is what I have:
void reverseList(nodePtr &theList)
{
nodePtr first= theList;// suppose first = {1, 2, 3}
nodePtr rest= first->next;// rest = {2, 3}

if (rest != NULL) reverseList(rest);//return;
// empty rest base case

// Recursively reverse the smaller {2, 3} case
// after: rest = {3, 2}
first->next->next = first; // put the first elem on the end of the list
first->next = NULL;
// (tricky step -- make a drawing)
theList = rest;
// fix the head pointer
}

This works fine but I am unable to think through how the last statement "theList=rest" keeps the head pointer at the new beginning of the list instead of recursively returning back to the initial position.

Yea, you are right, there needs to be an initial check to see if the next or the first is a NULL.

Pertaining to yours, rest will point to a NULL value after the recursion is complete--and so first->next->next = first becomes the next head, which therefore means that rest must be the rest of the link list.

On a sidenote, this may be a more intuitive way of doing it:

void reverseList(nodePtr &theList)
{
static nodePtr oldHead = theList, newHead;

if (theList->next != NULL) { reverseList(theList->next); theList->next->next = theList; }
else newHead = theList;
if (theList == oldHead) theList = newHead;
}

Crunchy cat yours works too after I put "theList->next=NULL" after "theList->next->next = theList;"

@thefountainhead

why does the 'rest' pointer not go back to the beginning of the list like the 'first' pointer after recursion.

for ex.
if we were to work on a 4 node list{1,2,3,4,Null}, after recursion 'first' ends up back at 1. Why does 'rest' point to 4 throughout without ending back at its initial value like 'first' does?

Crunchy cat yours works too after I put "theList->next=NULL" after "theList->next->next = theList;"


Cool. I did it in my head, so it's not surprising I missed the nullification.

Because the condition "if (rest != NULL) " is not satisfied-- the recursion breaks-- at the last node. So in the array {1,2,3,4}, the rest pointer will be at 4, and then the loop breaks. That value is unchanged and because you are passing the address of the list, the value is not discarded. So rest stays at the last value.

Ok this should do it.
void reverseList(node **theNode) // pass a pointer to the start node pointer
{
static node *startNode= *theNode, *endNode;
if((*theNode)->next != NULL)
{
reverseList(&((*theNode)->next));
(*theNode)->next->next = *theNode;
if(startNode == *theNode)
{
(*theNode)->next = NULL;
*theNode = endNode; // set the start node.
}

}else endNode = *theNode; // point to the new end node
}

Cool. I did it in my head, so it's not surprising I missed the nullification.

On second thought, the nullification was missed but just in the wrong spot.
By looking at it, it appears that it's only needed once we reach the original
head node (as this becomes the effective end of the list and we want to
nullify that to denote it as the end). My code would be adjusted as follows:

void reverseList(nodePtr &theList)
{
static nodePtr oldHead = theList, newHead;

if (theList->next != NULL) { reverseList(theList->next); theList->next->next = theList; }
else newHead = theList;
if (theList == oldHead) { theList->next = NULL; theList = newHead; }
}

Your code is close but you need to check your syntax..
The call reverseList(theList->next); should be reverseList(&theList->next); to name one of a few errors. But your code is on the correct track, I was going to use a counter but used your two static pointers.

PS not that its a great difference but you save one compare but moving the if (theList == oldHead) inside the "if (theList->next != NULL) {"

Your code is close but you need to check your syntax..
The call reverseList(theList->next); should be reverseList(&theList->next); to name one of a few errors. But your code is on the correct track, I was going to use a counter but used your two static pointers.

PS not that its a great difference but you save one compare but moving the if (theList == oldHead) inside the "if (theList->next != NULL) {"


It's using C++ parameter syntax so I think it may work (according to
the parameter structure that was listed; however, who knows... I could
be wrong. I am using my brain as a compiler here rather than a real one).

It is true that one compare is saved. For small lists the cost savings is
negligable; however, for a big list that could be alot of CPU cycles saved.
Optimize, optimize, optimize!