剑指Offer面试题6：从尾到头打印链表

// 面试题6：从尾到头打印链表
	// 题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。

#include <iostream>
#include <stack>

using namespace std;

struct ListNode{
	int m_nValue;
	ListNode *m_pNext;
};

void showList(ListNode *pHead);//打印链表 
void AddToTail(ListNode **pHead,int value);//尾部添加节点 
void RemoveNode(ListNode **pHead,int value); //删除节点

void PrintListRever(ListNode *pHead);//反向输出链表,利用栈 
void PrintListRever_Recur(ListNode *pHead);//反向输出链表,利用递归 


int main()
{
	
	ListNode *head = nullptr;
	AddToTail(&head,5);
	AddToTail(&head,3);
	AddToTail(&head,23);
	AddToTail(&head,97);
	AddToTail(&head,10);
	showList(head);
	
	/*
	RemoveNode(&head,3);
	showList(head);
	
	RemoveNode(&head,5);
	showList(head);
	
	RemoveNode(&head,10);
	showList(head);
	
	RemoveNode(&head,100);
	showList(head);
	*/
	
	PrintListRever(head);
	PrintListRever_Recur(head);
	
    return 0;
}

void PrintListRever(ListNode *pHead){
	if(pHead == nullptr)
		return;
	
	stack<int> nodes;
	while(pHead != nullptr){
		nodes.push(pHead->m_nValue);
		pHead = pHead->m_pNext;
	}
	
	while(!nodes.empty()){
		cout<<nodes.top()<<" ";
		nodes.pop();
	}
	cout<<endl;
}

void PrintListRever_Recur(ListNode *pHead){//反向输出,利用递归
	if(pHead != nullptr){
		if(pHead->m_pNext != nullptr){
			PrintListRever_Recur(pHead->m_pNext);
		}
	}
	
	cout<<pHead->m_nValue<<" ";
}



void showList(ListNode *pHead){
	while(pHead != nullptr){
		cout<<pHead->m_nValue<<" ";
		pHead = pHead->m_pNext;
	}
	cout<<endl;
}

void RemoveNode(ListNode **pHead,int value){
	if(pHead == nullptr || *pHead == nullptr)
		return;
	
	ListNode *pre = *pHead;
	if((*pHead)->m_nValue == value){
		*pHead = (*pHead)->m_pNext;
		delete pre;
		pre = nullptr;
		return;
	}
	else{
		ListNode *next = pre->m_pNext;	
		while(next != nullptr){
			if(next->m_nValue == value){
				pre->m_pNext = next->m_pNext;
				delete next;
				next = nullptr;
				return;
			}
			pre = next;
			next = next->m_pNext;	
		}	
	}		
}

void AddToTail(ListNode **pHead,int value){
	ListNode *pNew = new ListNode;
	pNew->m_nValue = value;
	pNew->m_pNext = nullptr;
	
	if(*pHead == nullptr){
		*pHead = pNew;
		return;
	}		
	
	ListNode *node = *pHead;
	while(node->m_pNext != nullptr){
		node = node->m_pNext;
	}
	node->m_pNext = pNew;
	
}