アルゴリズムの練習問題13:チェーンテーブルを反転する

タイトル:一方向チェーンテーブルを入力し、チェーンテーブルの最後からk番目のノードを出力します.チェーンテーブルの最後から0番目のノードはチェーンテーブルの最後のポインタです.チェーンテーブルノードの定義は以下の通りである:struct ListNode{int m_nKey;ListNode*m_pNext;};
上の問題は直接チェーンテーブル全体を遍歴して、総個数nを得ることができて、それからn-kは正のシーケンス番号を得ることができます.
あるいはチェーンテーブルを反転してから、正のk番目の要素を探します.
チェーンテーブルを反転する方法を3つ示します

//============================================================================
// Name        : RevertLink.cpp
// Author      : YLF
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

struct Node{
	int value;
	Node* next;
};

Node* head = NULL;


void Revert1(Node* pHead);
Node* Revert2(Node* p);
void Revert3(Node* p);
Node* addNode(Node* p, int value);
void printNode();

int main() {

	int input = 0;
	Node* cur = head;
	while(true){
		cin>>input;
		if(input!=-1)
			cur = addNode(cur, input);
		else
			break;
	}
	printNode();
	//Revert2(head)->next = NULL;
	//Revert1(head);
	Revert3(head);
	printNode();
	return 0;
}

/*
 *        ，            
 */
void Revert1(Node* pHead){
	if(pHead == NULL)
		return;
	Node* p1 = pHead;
	Node* p2 = p1->next;
	if(p2 == NULL)
		return;
	Node* p3 = p2->next;

	while(p2 != NULL){
		if(p1 == pHead)
			p1->next = NULL;
		p2->next = p1;
		p1 = p2;
		p2 = p3;
		if(p3)
			p3 = p3->next;
	}
	head = p1;
}

/*
 *        
 */
Node* Revert2(Node* p){
	if(p == NULL)
		return NULL;
	Node* temp = Revert2(p->next);
	if(temp != NULL)
		temp->next = p;
	else
		head = p;
	return p;

}

/*
 *      
 */
void Revert3(Node* p){
	Node* pCur = NULL;
	while(p!=NULL){
		Node* temp = new Node();
		temp->value = p->value;
		temp->next = NULL;

		if(pCur == NULL){
			pCur = temp;
		}else{
			temp->next = pCur;
			pCur = temp;
		}
		Node* delP = p;
		p = p->next;
		delete delP;
	}
	head = pCur;
}


/*
 *     
 */
Node* addNode(Node* p, int value){
	Node* temp = new Node();
	temp->value = value;
	temp->next = NULL;
	if(p == NULL){
		p = temp;
		head = temp;
	}
	else
		p->next = temp;
	return temp;
}

void printNode(){
	Node* p = head;
	while(p != NULL){
		cout<<p->value<<" ";
		p = p->next;
	}
	cout<<endl;
}