剑指offer面试题五—反向打印链表

剑指offer面试题5—反向打印链表

反向打印一个链表

链表不同于数组，内存并不连续，通过节点之间的指针进行连接，逆向打印的时候可以利用栈的特点，比较简单

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

struct ListNode
{
	ListNode * pNext;
	int Value;
};

int main()
{   
	stack<ListNode> NodeStory;
	int i = 0;
	const int length = 10;
	ListNode * pHead = new ListNode[length];
	ListNode * pNode = pHead;
	for (;i < (length-1); i++)
	{
		pNode->Value = i;
		ListNode * pNextNode = pNode+1;
		pNode->pNext = pNextNode;
		NodeStory.push(*pNode);
		pNode++;
	}
	pNode->Value = i;
	pNode->pNext = NULL;
	NodeStory.push(*pNode);

	while (!NodeStory.empty())
	{
		ListNode tempNode = NodeStory.top();
		cout << tempNode.Value<<" ";
		NodeStory.pop();
	}<pre name="code" class="cpp">        delete pHead;

return 0;}

既然用到栈，那么也就可以利用递归进行完成：

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

struct ListNode
{
	ListNode * pNext;
	int Value;
};

void PrintNode(ListNode * pHead)
{
	if (pHead != NULL)
	{
		if (pHead->pNext != NULL)
		{
			PrintNode(pHead->pNext);
		}
		cout << pHead->Value<<" ";
	}
}
int main()
{   
	stack<ListNode> NodeStory;
	int i = 0;
	const int length = 10;
	ListNode * pHead = new ListNode[length];
	ListNode * pNode = pHead;
	for (;i < (length-1); i++)
	{
		pNode->Value = i;
		ListNode * pNextNode = pNode+1;
		pNode->pNext = pNextNode;
		NodeStory.push(*pNode);
		pNode++;
	}
	pNode->Value = i;
	pNode->pNext = NULL;
	PrintNode(pHead);
	delete pHead;
	return 0;
}