#include <iostream> 
#include <vector>
using namespace std;


typedef struct ListNode {
	int data;
	struct ListNode * next;
	ListNode(int d) : data(d), next(NULL){}
};

ListNode *initList() {
	
	ListNode * head = NULL;
	ListNode * p = NULL;
	int number = 10;
	int i = 0;
	head = new ListNode(0);
	p = head;
	for	(i = 1; i < number; i++) {
		p->next = new ListNode(i);
		p = p->next;
	}
	return head;
	
} 

void printList(ListNode *head) {
	
	ListNode * p = head;
	if (!head){
		return;
	}
	while (p && p->next) {
		cout<<p->data<<"->";
		p = p->next; 
	}
	if (p) {
		cout<<p->data<<endl;
	}
	
}

//using vector to store the ListNode->data, and print it from the end to start
void reversePrintListUsingVector(ListNode *head){
	vector <int> vec;
	if(!head) {
		return;
	}
	ListNode *p = head;
	while (p) {
		vec.push_back(p->data);
		p = p->next;
	}
	for (vector<int>::size_type i = vec.size() - 1; i > 0; i--) {	
		cout<<vec[i]<<"->";				
	}
	cout<<vec[0]<<endl;
	
} 

//change the ListNode:delete the head->next and insert the deleted node after the newHead;
ListNode *reversePrintList(ListNode *head){
	
	if(!head) {
		return NULL;
	}
	
	
	ListNode *deletedNode = head;
	ListNode *oldHead = head;
	
	ListNode *tempHead = new ListNode(0);

	while(oldHead) {
		deletedNode = oldHead; 
		oldHead = oldHead->next;		
		deletedNode->next = tempHead->next;
		tempHead->next = deletedNode;
	}
	
	ListNode * reserverdhead = tempHead->next;
	delete tempHead; 

	return reserverdhead; 
	
} 


int main(){ 

/********In the first way, the List was not changed, but we need a vector to store the list*************/
	ListNode * head = initList();
	cout<<"initial List:"<<endl;
	printList(head);
	
	cout<<"the first way to reverse the List:"<<endl;
	reversePrintListUsingVector(head);

/********In the second way, the List was changed and we need to new a listNode*************/
	cout<<endl;
	cout<<"initial List:"<<endl;
	printList(head);
	cout<<"the second way to reverse the List:"<<endl;	
	head = reversePrintList(head);
	printList(head);
	

	
	
}

05_从尾到头打印链表