链表倒序输出

#include <iostream>

#include <stack>

using namespace std;

struct ListNode

{

int        m_nValue;

ListNode*  m_pNext;

//构造函数初始化

ListNode(int a);

int GetLength(ListNode *head);

};

ListNode::ListNode(int a) : m_nValue(a), m_pNext(0)

{

}

int GetLength(ListNode* head)

{

ListNode* pNode = head;

int nLen = 0;

while (pNode != NULL)

{

nLen++;

pNode = pNode->m_pNext;

}

return nLen;

}

//数组

void PrintListBack(ListNode* head)

{

int n = GetLength(head);

ListNode** p = new ListNode*[n + 1];

p[n] = NULL;

int i = 0;

ListNode* pNode = head;

while (i < n)

{

p[i] = pNode;

pNode = pNode->m_pNext;

++i;

}

for (i = n - 1; i >= 0; i--)

{

cout << p[i]->m_nValue << " ";

}

}

//栈

void PrintListBack2(ListNode* head)

{

stack<ListNode> listStack;

ListNode* pNode = head;

while (pNode != NULL)

{

listStack.push(pNode->m_nValue);

pNode = pNode->m_pNext;

}

int i = listStack.size();

for (; i>0; i--)

{

ListNode p = listStack.top();

cout << p.m_nValue << endl;

listStack.pop();

}

}

//反转链表

void PrintListBack3(ListNode* head)

{

stack<ListNode*> listStack;

ListNode* pNode = head;

while (pNode != NULL)

{

listStack.push(pNode);

pNode = pNode->m_pNext;

}

int i = listStack.size();

for (; i>0; i--)

{

ListNode* p = listStack.top();

cout << p->m_nValue << endl;

listStack.pop();

}

}

//递归

void PrintListBack4(ListNode* head)

{

if (head != NULL)

{

if (head->m_pNext != NULL)

{

PrintListBack4(head->m_pNext);

}

cout << head->m_nValue << endl;

}

}

int main(int argc, char* argv[])

{

ListNode*  head = new ListNode(0);

ListNode*  node1 = new ListNode(1);

ListNode*  node2 = new ListNode(2);

ListNode*  node3 = new ListNode(3);

ListNode*  node4 = new ListNode(4);

ListNode*  node5 = new ListNode(5);

head->m_pNext = node1;

node1->m_pNext = node2;

node2->m_pNext = node3;

node3->m_pNext = node4;

node4->m_pNext = node5;

node5->m_pNext = NULL;

int n = GetLength(head);

cout << "个数为：" << n << endl;

PrintListBack4(head);

getchar();

return 0;

}