#include "stdafx.h"
//A singleList traverse algorithem using the recursive method
#define MAXLEN 10
class ListNode
{
public:
?? ?friend class List;
?? ?ListNode():link(NULL){};
?? ?ListNode(const int& item):data(item),link(NULL){};
?? ?~ListNode();
private:
?? ?int data;
?? ?ListNode* link;
};
class List
{
public:
?? ?List():head(NULL),Length(0){};
?? ?List(ListNode* h):head(h){};
?? ?bool ListInitialize();
?? ?void Reverse1(ListNode*);
?? ?void Reverse2();
private:
?? ?ListNode* head;
?? ?int Length;
};
bool List::ListInitialize()
{
?? ?ListNode* new_node;
?? ?ListNode* curr_node = head;
?? ?while(Length < MAXLEN)
?? ?{
?? ??? ?new_node = new ListNode(getchar());
?? ??? ?if (curr_node == NULL)
?? ??? ?{
?? ??? ??? ?head = curr_node = new_node;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?curr_node->link = new_node;
?? ??? ??? ?curr_node = new_node;
?? ??? ?}
?? ??? ?Length++;
?? ?}
?? ?return true;
}
//Recursive reverse
void List::Reverse1(ListNode* prenode)? //we must pass the prenode to the next traverse
{
?? ?ListNode *currnode;
?? ?currnode = head;
?? ?if(head = NULL) return;
?? ?if(currnode->link == NULL)
?? ?{
?? ??? ?head = currnode;
?? ??? ?currnode->link = prenode;
?? ?}
?? ?else
?? ?{?? ??? ?
?? ??? ?head = currnode->link;
?? ??? ?currnode->link = prenode;
?? ??? ?Reverse1(currnode);? //currnode is acting as prenode of the next traverse
?? ?}
}
int main()
{
?? ?List newList;
?? ?newList.ListInitialize();
?? ?newList.Reverse1(NULL);
?? ?return 0;
}