剑指offer（3）——C++实现链表的反向输出

拼搏现实的明天。 2021-11-11 08:58 111阅读 0赞

# 题目描述 #

给定一个链表，反向输出。

# 考察知识 #

*  链表的创建以及常规操作
 *  栈的使用

# 解题思路 #

先进去的后输出，自然想到是栈的特点，故使用栈来实现。递归的本质也是栈。

# 完整代码 #

/*03_printlist*/
    #include<iostream>
    #include<vector>
    #include<stack>
    using namespace std;
     struct ListNode 
     {
        
            int val;
            struct ListNode *next;
            ListNode(int x) :
                  val(x), next(NULL) {
        
            }
      };
    
    class Solution {
        
    public:
    	vector<int> printListFromTailToHead(ListNode* head) 
    	{
        
    		stack<int> nodes;
    		vector<int> value;
    		ListNode* pNode = head;
    		while (pNode != NULL) //压栈
    		{
        
    			nodes.push(pNode->val);
    			pNode = pNode->next;
    		}
    		while (!nodes.empty())//出栈
    		{
        
    			value.push_back(nodes.top());
    			nodes.pop();
    		}
    		return value;
    	}
    };
    int main()
    {
        
    	ListNode* p1 = new ListNode(1);
    	ListNode* p2 = new ListNode(2);
    	ListNode* p3 = new ListNode(3);
    	p1->next = p2;
    	p2->next = p3;
    	Solution s;
    	vector<int> value = s.printListFromTailToHead(p1);
    	for (int i = 0; i < value.size() ; i++)
    	{
        
    		cout << value[i];
    	}
    	cout << endl;
    	return 0;
    }

# 编写遇到的问题 #

*  链表的创建  
    单链表包含本身的值和指向下一个节点的指针next。简单的创建过程如下：

ListNode* p1 = new ListNode(1);
    	ListNode* p2 = new ListNode(2);
    	ListNode* p3 = new ListNode(3);
    	p1->next = p2;
    	p2->next = p3;

*  栈的使用  
    要使用栈首先要添加stack头文件，其次要建立一个栈`stack<T> s`然后对其进行操作。常见操作如下：  
    `s.push()`将数据要入栈中  
    `s.pop()`将栈顶元素弹出（弹出就没有这个元素了）  
    `s.top()`获取栈顶元素（未弹出）
 *  vector容器  
    vector容器也可使用`size`来输出大小  
    `vector.push_back` 在容器尾部加入元素