剑指offer：逆置打印链表

短命女 2022-05-23 06:42 173阅读 0赞

**从尾到头打印链表**  
**题目描述：**

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

**解题思路：**

1.通过借助容器vector和栈stack共同完成 ----后进先出 
    2.不使用栈结构stack,直接利用翻转函数reverse()函数和容器vector 
    3.不使用容器vector,直接用print结合递归方式实现链表的反向打印

**相关代码：**

//链表结构体定义
    struct ListNode {
            int val;
            struct ListNode *next;
            ListNode(int x) :
                  val(x), next(NULL) {
            }
    };

//方法一：通过借助容器vector和栈stack共同完成 ----后进先出
    class Solution {
    public:
        vector<int> printListFromTailToHead(struct ListNode* head) {
    
            vector<int> result;//存储输出的节点的值
            stack<struct ListNode*> nodes;//用栈来存储每个节点
    
            struct ListNode* pNode = head;//从链表头开始
            while (pNode != NULL){            //链表的所有节点全部入栈
                nodes.push(pNode);
                pNode = pNode->next;
            }
    
            while (!nodes.empty()){            //出栈：后进先出
                pNode = nodes.top();
                result.push_back(pNode->val);
                nodes.pop();
            }
            return result;
        }
    };

//方法二： 不使用栈结构stack,直接利用翻转函数reverse()函数和容器vector 
    class Solution{
    public:
        vector<int> printListFromTailToHead(struct ListNode* head){
            vector<int> result;    // 存储输出节点的值
            struct ListNode* pNode=head;
    
            while(pNode!=NULL){
                result.push_back(pNode->val);
                pNode=pNode->next;
            }
    
            reverse(result.begin(),result.end());
            return result;
        }
    };

//方法三： 不使用容器vector,直接用print结合递归方式实现链表的反向打印
    class Solution
    {
    public:
        void printListFromTailToHead(ListNode* pHead)
        {
            if(pHead!=NULL)
            {
               //print the next node first
                if(pHead->next!=NULL)
                {
                    printListFromTailToHead(pHead->next);    
                }
            // And then print the current node
            print("%d",pHead->val);
            }
        }
    };