//面试题5
//从尾到头输出链表

#include <stdio.h>
#include <iostream>
#include <stack>
using namespace std;


typedef struct ListNode
{
	int m_nkey;
	struct ListNode *m_pnext;
}ListNode;

bool DisplayList1(ListNode *Head)
{
	//第一种情况，允许更改链表结构（将链表进行转置）
	
	ListNode *pDummy = new ListNode;
	pDummy->m_nkey = 0;
	pDummy->m_pnext = Head;

	ListNode *pCurrent = Head;
	while (pCurrent != NULL && pCurrent->m_pnext != NULL)   //链表转置
	{
		ListNode *pTemp = pCurrent->m_pnext;
		pCurrent->m_pnext = pTemp->m_pnext;
		pTemp->m_pnext = pDummy->m_pnext;
		pDummy->m_pnext = pTemp;	
	}
	//进行输出
	Head = pDummy->m_pnext;
	while (Head != NULL)
	{
		cout << Head->m_nkey << endl;
		Head = Head->m_pnext;
	}
	return true;
}

bool DisplayList2(ListNode *List)
{
//第二种情况，不允许改变链表结构（就要用到栈，先进后出）
	stack<ListNode *> sList;
	
	while (List != NULL)
	{
		sList.push(List);   //入栈
		List = List->m_pnext;
	}

    //依次出栈
	while (!sList.empty())
	{
		cout << sList.top()->m_nkey << endl;
		sList.pop();
	}

	return true;
}


ListNode* DisplayList3(ListNode *Head)
{
	//用递归的方式从尾到头输出链表
	if (Head == NULL)
	{
		return NULL;
	}
	if (Head->m_pnext == NULL)
	{
		return Head;
	}
	else
	{
		ListNode *newhead = DisplayList3(Head->m_pnext);
		Head->m_pnext->m_pnext = Head;
		Head->m_pnext = NULL;

		return newhead;
	}
}
int main(void)
{
	ListNode *pHead1 = new ListNode;
	ListNode *pHead2 = new ListNode;
	ListNode *pHead3 = new ListNode;
	pHead1->m_nkey = 1;
	pHead1->m_pnext = pHead2;
	pHead2->m_nkey = 2;
	pHead2->m_pnext = pHead3;
	pHead3->m_nkey = 3;
	pHead3->m_pnext = NULL;

	ListNode *Head = DisplayList3(pHead1);

	return 0;



}