/*********************************************************
题目:输入一个链表的头结点,从为到头反过来打印每个节点的值
**********************************************************/
#include <iostream>
#include <stack>
using namespace std;
struct ListNode{
int m_nKey;
ListNode* m_pNext;
};
//添加节点
void addToTail(ListNode** pHead, int value)
{
ListNode* pNode = new ListNode();
pNode->m_nKey = value;
pNode->m_pNext = NULL;
if(*pHead == NULL)
{
*pHead = pNode;
}
else
{
ListNode* pCurrentNode = *pHead;
while(pCurrentNode->m_pNext != NULL)
pCurrentNode = pCurrentNode->m_pNext;
pCurrentNode->m_pNext = pNode;
}
}
/*
版本1:需要改进之处1)形参类型;2)头指针处理
//以相反顺序打印链表
void printListInReversedOrder(ListNode** pHead)
{
if(pHead == NULL || *pHead == NULL)
return;
stack<ListNode*> listStack;
ListNode* pCurrentNode = *pHead;
if( pCurrentNode == *pHead)
listStack.push(pCurrentNode);
while(pCurrentNode->m_pNext != NULL)
{
listStack.push(pCurrentNode->m_pNext);
pCurrentNode = pCurrentNode->m_pNext;
}
while(!listStack.empty())
{
pCurrentNode = listStack.top();
cout << pCurrentNode->m_nKey << '\t';
listStack.pop();
}
}
*/
/*版本2:处理链表时,当不改变链表结构时,形参设为ListNode* pHead足够
void printListInReversedOrder(ListNode* pHead)
{
if(pHead == NULL)
return;
stack<ListNode*> nodes;
ListNode* pNode = pHead;
while(pNode != NULL) //将遍历过的数进栈
{
nodes.push(pNode);
pNode = pNode->m_pNext;
}
while(!nodes.empty()) //将栈内的数据出栈,然后显示
{
pNode = nodes.top();
cout << pNode->m_nKey << '\t';
nodes.pop();
}
}
*/
void printListInReversedOrder(ListNode* pHead)
{
if(pHead == NULL)
return;
if(pHead->m_pNext != NULL)
printListInReversedOrder(pHead->m_pNext);
cout << pHead->m_nKey << '\t';
}
//单元测试
//一般情况
void test1()
{
ListNode* pRoot = NULL;
addToTail(&pRoot,5);
addToTail(&pRoot,7);
addToTail(&pRoot,3);
addToTail(&pRoot,9);
addToTail(&pRoot,1);
printListInReversedOrder(pRoot);
}
//只有一个节点
void test2()
{
ListNode* pRoot = NULL;
addToTail(&pRoot,5);
printListInReversedOrder(pRoot);
}
//空链表
void test3()
{
ListNode* pRoot = NULL;
printListInReversedOrder(pRoot);
}
int main()
{
test1();
cout << endl;
test2();
cout << endl;
test3();
return 0;
}
这里的问题很显然是先进后出的问题,所以使用栈来实现。每经过一个节点,就将它放入栈中。当遍历完整个链表后,
再从栈顶开始逐个输出节点的值,此时输出的节点的顺序就是倒序。
这里自己实现了版本1,参见答案后,又给出了版本2。
又由于递归的本质就是一个栈结构,所以也可用用递归实现,如版本3。
==参见剑指offer
分享到:
相关推荐
输入一个链表,从尾到头打印链表每个节点的值。 输入: 每个输入件仅包含一组测试样例。 每一组测试案例包含多行,每行一个大于0的整数,代表一个链表的节点。第一行是链表第一个节点的值,依次类推。当输入到-1时...
C++版本从头到尾或者从尾到头打印链表原理及代码实现
剑指 Offer 06. 从尾到头打印链表链接:
C语言实现 从尾到头打印链表 递归 反转链表
从尾到头打印链表.md
python 实现 从尾到头打印链表
从尾到头打印链表输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。示例 1:输出:[2,3,1]"* Definition for singl
java基础面试题从尾到头打印链表本资源系百度网盘分享地址
剑指 Offer 06. 从尾到头打印链表原题链接:剑指 Offer 06. 从尾到头打印链表代码* Definition for singly-linked
剑指Offer - 03 - 从尾到头打印链表题目链接题目输入一个链表的头结点,按链表值从尾到头的顺序返回一个ArrayList。递归的写法:public cl
leetcode
剑指 Offer 06. 从尾到头打印链表输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。示例 1:输出:[2,3,1]辅助栈// 辅助栈s
剑指 Offer 06. 从尾到头打印链表题目描述:输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。思路:链表只能够由前向后遍历,但是我们要
剑指 Offer 06. 从尾到头打印链表python(csdn)————程序
js代码-链表(从尾到头打印链表)
主要介绍了Java编程实现从尾到头打印链表代码实例,小编觉得挺不错的,这里分享给大家,供需要的朋友参考。
输入链表的第一个节点,从尾到头反过来打印出每个结点的值。02.问题分析对于这种颠倒顺序的问题,我们应该就会想到栈,后进先出。所以,这一题要么自己使用栈,要么让系
题目地址:从尾到头打印链表 题目描述 输入一个链表,按链表从尾到头的顺序返回一个ArrayList。 题目解析 方法一: 因为题目要求返回的顺序是从尾到头,所以我们可以采用递归的形式访问链表,在回归的过程才将节点的...
题目:输入一个链表,按链表从尾到头的顺序返回一个ArrayList 先存入数组再将数组逆序打印 我的思路是将链表内容先存到一个中间数组,再将这个中间数组逆序放入结果数组中(也可以直接进行数组翻转) /*function ...
利用栈的先进后出的特点解法二 不用栈,用递归递归访问当前节点的下一个节点,打印的时候就反过来了PrintListReverse(head->next);vect