【C/C++练习题】从尾到头打印链表

举报
王建峰 发表于 2021/11/19 02:12:29 2021/11/19
【摘要】 《剑指Offer》面试题6   1 问题 题目:输入一个链表的头结点,从尾到头反过来打印出每个结点的值。     2 分析 方式一:可先将链表的节点和指针进行反转,不过这样操作也改变了链表结构。 方式二:通过栈后入先出的规律,将节点通过栈结构,进行打印。 方式三:通过构造递归函数,实现链表...

《剑指Offer》面试题6

1 问题

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

2 分析

方式一:可先将链表的节点和指针进行反转,不过这样操作也改变了链表结构。

方式二:通过栈后入先出的规律,将节点通过栈结构,进行打印。

方式三:通过构造递归函数,实现链表的逆向打印。

3 代码


      #include "iostream"
      #include "stack"
      using namespace std;
      typedef struct node
      {
     	int m_nValue;
      	node* m_pNext;
      }ListNode;
      //功能:通过栈结构将链表逆向打印
      //输入:pHead 头节点地址
      //输出:无
      void PrintListReversingly_Iteratively(ListNode* pHead)
      {
      	std:stack<ListNode*> nodes;	//通过stack容器定义栈结构 nodes
      	ListNode* pNode = pHead;
     	while (pNode != nullptr)
      	{//1.顺序遍历链表节点,将节点压如栈中
      		nodes.push(pNode);		//将pNode压入栈中
      		pNode = pNode->m_pNext;
      	}
     	while (!nodes.empty())
      	{//2.依次从栈中取出元素,并打印节点的值
      		pNode = nodes.top();			//从栈中弹出一个元素
      		cout << pNode->m_nValue << ",";
      		nodes.pop();					//移除栈顶元素
      	}
      	cout << endl;
      }
      //功能:通过递归的思想将链表节点逆序输出
      //输入:pHead 头节点地址
      //返回:无
      void PrintListReversingly_Recursively(ListNode* pHead)
      {
     	if (pHead != nullptr)
      	{
     		if (pHead->m_pNext != nullptr)	//回归条件(到达尾部节点)
      		{
     			PrintListReversingly_Recursively(pHead->m_pNext);	//递推公式
      		}
      		cout << pHead->m_nValue << ",";	//打印节点信息
      	}
      }
      void test01()
      {
      	ListNode* pHead  = NULL;
          ListNode* pNode1 = NULL;
          ListNode* pNode2 = NULL;
          ListNode* pNode3 = NULL;
          pHead = (ListNode*)malloc(sizeof(ListNode));
          pNode1 = (ListNode*)malloc(sizeof(ListNode));
          pNode2 = (ListNode*)malloc(sizeof(ListNode));
          pNode3 = (ListNode*)malloc(sizeof(ListNode));
     	if (pHead == NULL || pNode1 == NULL || pNode2 == NULL || pNode3 == NULL)
      	{
      		cout << "malloc fail" << endl;
     		return ;
      	}
      	pHead->m_nValue = 0;
      	pHead->m_pNext  = pNode1;
      	pNode1->m_nValue = 1;
      	pNode1->m_pNext  = pNode2;
      	pNode2->m_nValue = 2;
      	pNode2->m_pNext  = pNode3;
      	pNode3->m_nValue = 3;
      	pNode3->m_pNext  = NULL;
      	cout << "方法1:";
     	PrintListReversingly_Iteratively(pHead);	//方法1
      	cout << "方法2:";
     	PrintListReversingly_Recursively(pHead);	//方法2
      	cout << endl;
      }
      int main(int argc, char const *argv[])
      {
     	test01();
     	return 0;
      }
  
 

4 运行

文章来源: blog.csdn.net,作者:hinzer,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/feit2417/article/details/96823864

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。