《剑指offer》面试题06：从尾到头打印链表

本文主要是介绍《剑指offer》面试题06：从尾到头打印链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

更多剑指offer面试习题请点击：《剑指offer》（第二版）题集目录索引

题目：
　　输入一个链表的头结点，从尾到头反过来打印出每个结点的值。

解题思路：
　　关于这题我们可以用三种方法解决：
　　1. 栈
　　2. 递归
　　3. 循环

< code1_stack>

void PrintListReversingly_Iteratively(ListNode* pHead)
{std::stack<ListNode*> nodes;ListNode* pNode = pHead;while (pNode != nullptr){nodes.push(pNode);pNode = pNode->m_pNext;}while (!nodes.empty()){pNode = nodes.top();printf("%d\t", pNode->m_nKey);nodes.pop();}
}

< code2_Recursively >

void PrintListReversingly_Recursively(ListNode* pHead)
{if (pHead != nullptr){if (pHead->m_pNext != nullptr){PrintListReversingly_Recursively(pHead->m_pNext);}printf("%d\t", pHead->m_nKey);}
}

< code3_Loop >

void PrintListReversingly_Loop(ListNode* pHead)
{if (pHead != nullptr){ListNode* cur = pHead;ListNode* tail = nullptr;while (tail != pHead){cur = pHead;while (cur->m_pNext != tail){cur = cur->m_pNext;}printf("%d\t", cur->m_nKey);tail = cur;}}
}

< Test code>


void PrintList(ListNode* pNode)
{if (pNode != nullptr){printf("%d", pNode->m_nKey);}
}ListNode* CreateListNode(int value)
{ListNode* tmp = new ListNode;tmp->m_nKey = value;tmp->m_pNext = nullptr;return tmp;
}void ConnectListNodes(ListNode* pNode1, ListNode* pNode2)
{if (pNode1 != nullptr){pNode1->m_pNext = pNode2;}
}void DestroyList(ListNode* pHead)
{ListNode* pNext = nullptr; while (pHead != nullptr){pNext = pHead->m_pNext;delete pHead;pHead = pNext;}pHead = nullptr;
}void Test(ListNode* pHead)
{//PrintList(pHead);PrintListReversingly_Iteratively(pHead);printf("\n");PrintListReversingly_Recursively(pHead);printf("\n");PrintListReversingly_Loop(pHead);
}// 1->2->3->4->5
void Test1()
{printf("\nTest1 begins.\n");ListNode* pNode1 = CreateListNode(1);ListNode* pNode2 = CreateListNode(2);ListNode* pNode3 = CreateListNode(3);ListNode* pNode4 = CreateListNode(4);ListNode* pNode5 = CreateListNode(5);ConnectListNodes(pNode1, pNode2);ConnectListNodes(pNode2, pNode3);ConnectListNodes(pNode3, pNode4);ConnectListNodes(pNode4, pNode5);Test(pNode1);DestroyList(pNode1);
}// 只有一个结点的链表: 1
void Test2()
{printf("\nTest2 begins.\n");ListNode* pNode1 = CreateListNode(1);Test(pNode1);DestroyList(pNode1);
}// 空链表
void Test3()
{printf("\nTest3 begins.\n");Test(nullptr);
}int main(int argc, char* argv[])
{Test1();Test2();Test3();system("pause");return 0;
}