题目
输入一个链表的头节点，从尾到头反过来打印出来每个节点的值。链表节点定义如下：
struct ListNode { int m_nKey; struct ListNode* m_pNext; };
思路
栈方法
从尾到头完全符合栈的特性，我们直接拿栈来存储就可以顺利输出。(c语言需要自己构造栈，这块用数组代替。这里就只构造一个链表)
C
#include<stdio.h> #include<stdlib.h> #include<time.h> struct ListNode { int m_nKey; struct ListNode* m_pNext; }; /* 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */ void CreateListTail(struct ListNode** L, int n) { struct ListNode* p; struct ListNode* r; int i; srand((unsigned int)time(NULL)); /* 初始化随机数种子 */ *L = (struct ListNode*)malloc(sizeof(struct ListNode)); /* L为整个线性表 */ r = *L; /* r为指向尾部的结点 */ for (i = 0; i < n; i++) { p = (struct LilstNode*)malloc(sizeof(struct ListNode)); /* 生成新结点 */ if (NULL == (*L)) { perror("开辟子节点空间失败"); } p->m_nKey = rand() % 10; /* 随机生成100以内的数字 */ r->m_pNext = p; /* 将表尾终端结点的指针指向新结点 */ r = p; /* 将当前的新结点定义为表尾终端结点 */ } r->m_pNext = NULL; /* 表示当前链表结束 */ } /* 初始条件：链式线性表L已存在 */ /* 操作结果：依次对L的每个数据元素输出 */ void ListTraverse(struct ListNode* L) { struct ListNode* p = L->m_pNext; while (p != NULL) { printf("%d ", p->m_nKey); p = p->m_pNext; } printf("\n"); } void PrintListReversing(struct ListNode* L) { int* n = (int*)malloc(10 * sizeof(int)); int size = 0; //实际元素个数 int length = 10; //数组长度 struct ListNode* p = L->m_pNext; while (p != NULL) { if (size + 1 == length)//扩容 { length += 10; int* tmp = (int*)realloc(n, length * sizeof(int)); if (NULL == tmp) { perror("扩充失败！"); } n = tmp; tmp = NULL; } n[size++] = p->m_nKey; p = p->m_pNext; } for (int i = size - 1; i >= 0; i--) { printf("%d ", n[i]); } } int main() { struct ListNode* L; CreateListTail(&L, 10); printf("从前到后打印\n"); ListTraverse(L); printf("从尾到头打印\n"); PrintListReversing(L); return 0; }
C++
#include <string> #include <iostream> #include <stack> using namespace std; class Node { public: int data; Node* next; }; class LinkList { public: LinkList(); ~LinkList(); int CreateLinkList(int size); int BYELinkList(); int TravalLinkList(); Node* head; int size; }; LinkList::LinkList() { head = new Node; head->data = 0; head->next = NULL; size = 0; } LinkList::~LinkList() { delete head; } int LinkList::CreateLinkList(int n)//创建链表 { if (n < 0) { printf("error\n"); return -1; } Node* ptemp = NULL; Node* pnew = NULL; this->size = n; ptemp = this->head; for (int i = 0; i < n; i++) { pnew = new Node; pnew->next = NULL; cout << "输入第" << i + 1 << "个节点值" << endl; cin >> pnew->data; ptemp->next = pnew; ptemp = pnew; } cout << "创建完成" << endl; return 0; } int LinkList::BYELinkList()//销毁链表 { Node* ptemp = NULL; if (this->head == NULL) { cout << "链表原本就为空" << endl; return -1; } while (this->head) { ptemp = head->next; delete head; head = ptemp; } cout << "销毁链表完成" << endl; return 0; } int LinkList::TravalLinkList()//输出链表 { Node* ptemp = this->head->next; if (this->head == NULL) { cout << "链表为空" << endl; return -1; } while (ptemp) { cout << ptemp->data << "->"; ptemp = ptemp->next; } cout << "NULL" << endl; return 0; } void PrintListReversing(Node* list)//从尾到头打印 { stack<int> nodes; Node* ptemp = list->next; while (ptemp != NULL) { nodes.push(ptemp->data); ptemp = ptemp->next; } int temp = 0; cout << "从尾到头打印链表" << endl; while (nodes.empty() == false)//不为空 { temp = nodes.top(); cout << temp << " "; nodes.pop(); } cout << endl; } int main(void) { LinkList list; LinkList* plist = &list; plist->CreateLinkList(5); plist->TravalLinkList(); PrintListReversing(plist->head); plist->BYELinkList(); system("pause"); return 0; }
递归法
递归的本质就是栈结构，所以很自然的想到了用递归实现，我们访问到一个节点的时候，先递归输出后面的节点，在输出自身节点。
但是递归会有一个问题，当链表非常长的时候，就会导致函数调用的层级很深，从而导致函数调用栈溢出。显眼用栈基于循环实现的代码的鲁棒性要好一些。
C++
#include <string> #include <iostream> #include <stack> using namespace std; class Node { public: int data; Node* next; }; class LinkList { public: LinkList(); ~LinkList(); int CreateLinkList(int size); int BYELinkList(); int TravalLinkList(); Node* head; int size; }; LinkList::LinkList() { head = new Node; head->data = 0; head->next = NULL; size = 0; } LinkList::~LinkList() { delete head; } int LinkList::CreateLinkList(int n)//创建链表 { if (n < 0) { printf("error\n"); return -1; } Node* ptemp = NULL; Node* pnew = NULL; this->size = n; ptemp = this->head; for (int i = 0; i < n; i++) { pnew = new Node; pnew->next = NULL; cout << "输入第" << i + 1 << "个节点值" << endl; cin >> pnew->data; ptemp->next = pnew; ptemp = pnew; } cout << "创建完成" << endl; return 0; } int LinkList::BYELinkList()//销毁链表 { Node* ptemp = NULL; if (this->head == NULL) { cout << "链表原本就为空" << endl; return -1; } while (this->head) { ptemp = head->next; delete head; head = ptemp; } cout << "销毁链表完成" << endl; return 0; } int LinkList::TravalLinkList()//输出链表 { Node* ptemp = this->head->next; if (this->head == NULL) { cout << "链表为空" << endl; return -1; } while (ptemp) { cout << ptemp->data << "->"; ptemp = ptemp->next; } cout << "NULL" << endl; return 0; } void PrintListReversing(Node* list)//从尾到头打印 { if (NULL != list) { if (list->next != NULL) { PrintListReversing(list->next); } cout << list->data << " "; } } int main(void) { LinkList list; LinkList* plist = &list; plist->CreateLinkList(5); plist->TravalLinkList(); PrintListReversing(plist->head->next); plist->BYELinkList(); system("pause"); return 0; }
本章完！
