题目概述

设计一个函数，输入一个链表的头结点，从尾到头来打印该链表

链表的节点定义如下

//节点的定义 struct ListNode { int m_data; ListNode* m_pNext; };

考点

该题目考察面试者对栈、递归以及循环三方面的相互关联的概念

以及对单链表的编程能力

实现一个简单的单链表

void InitList(ListNode** phead) { *phead = NULL; } ListNode* BuyNewNode(int data) { ListNode* newNode = NULL; newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->m_data = data; newNode->m_pNext = NULL; return newNode; } void PushBack(ListNode** phead, int data) { assert(phead); ListNode* newNode = BuyNewNode(data); if (*phead == NULL) { *phead = newNode; return; } ListNode* cur = *phead; while (cur->m_pNext) cur = cur->m_pNext; cur->m_pNext = newNode; } void PrintList(ListNode* phead) { assert(phead); ListNode* cur = phead; while (cur) { printf("%d ", cur->m_data); cur = cur->m_pNext; } printf("\n"); }

逆序打印单链表

递归实现

//递归实现 void ReversePrint(ListNode* phead) { if (phead == NULL) return; ReversePrint(phead->m_pNext); printf("%d ", phead->m_data); }

非递归实现

//非递归实现 #include<stack> void ReversePrintNonR(ListNode* phead) { assert(phead); stack<ListNode*> s; ListNode* cur = phead; while (cur) { s.push(cur); cur = cur->m_pNext; } while (!s.empty()) { printf("%d ", s.top()->m_data); s.pop(); } printf("\n"); }

测试用例

void TestList() { ListNode* phead; InitList(&phead); PushBack(&phead, 1); PushBack(&phead, 2); PushBack(&phead, 3); PushBack(&phead, 4); PrintList(phead); ReversePrintNonR(phead); ReversePrint(phead); }