劍指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;
}