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

《剑指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