#ifndef LIST_H
#define LIST_H
class List
{
private: // can only be accessed by functions declared here
typedefstruct node
{
int data;
node* next; //node pointer, purpose is to point to another node
}* nodePtr;
//typedef struct node* nodePtr; //type nodePtr, same as struct node*
nodePtr head;
nodePtr curr;
nodePtr temp;
public: // This is where functions go
List(); // Constructor, sets initial values of NodePtr
void AddNode(int addData);
void DeleteNode(int delData);
void PrintList();
void ReverseList();
void callReverse();
void ReverseRec(node* pointer);
};
#endif /* LIST_H */
I have got the iterative way of reversing the Linked List correct, but when I tried to implement the recursive way, I am running into an issue where the initial head value is missing from my print function.
For example: 3 5 7 -> callReverse -> printList -> 7 5 (missing the 3)
Here is the code for my Linked List functions below:
The code in question is ReverseRec and callReverse (both required for recursive calls)
void List::callReverse(){
nodePtr h = head;
head = nullptr;
ReverseRec(h);
}
void List::ReverseRec(nodePtr pointer)
{
nodePtr temp = new node;
temp->data = pointer->data; // copy the data
temp->next = nullptr; // prevent that we create a graph with a loop instead of a list
if(pointer->next == nullptr) // we found the tail node, this should be the first node to add to the reversed list
{
head = temp; // add this node to the reversed list
curr = head; // and make it simple to add another node if there are more
}
else // this is not the first node to add to the reversed list
{
ReverseRec(pointer->next); // it is this nodes turn when this function call returns
curr->next = temp; // finally add it
curr = temp; // and make it simple to add another node if there are more
}
}
I think if you take lines 114 and 115 and move them to after the curly brace on line 116 your program will work. The problem is, you are only adjusting the next pointers when head == NULL which won't be true at this point in the recursive call except for in the last recursion.