剑指Offer_06_从尾到头打印链表

题目1描述：

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

链表节点定义如下：
struct ListNode {

    int m_nKey;
    ListNode* m_pNext;
};

解法1：反转链表

看到这道题后，很多人的第一反应是将链表中链接节点的指针反转过来，改变链表的方向，然后就可以从头到尾输出了，但该方法会改变原来链表的结构，是否允许在打印链表的时候修改链表的结构？这取决于面试官的要求，因此在面试的时候我们要询问清楚面试官的要求。

⭐️在面试中，如果我们打算修改输入的数据，最好先问面试官是不是允许修改

解法2：栈

通常打印是一个只读操作，我们不希望打印时修改内容，假设面试官也要求这个题目不能改变链表的结构

//栈：后进先出
//每经过一个节点的时候，把该节点放到一个栈中，当遍历完整个链表后，再从栈顶开始逐个输出节点的值，此时输出的节点的顺序已经反转过来了
void PrintListReversingly_Iteratively(ListNode* pHead)
{
    std::stack<ListNode*> nodes;  //定义一个栈，栈名为nodes

    ListNode* pNode = pHead;  //声明一个指针指向头节点
  
    //只要该指针不为空，就将该指针指向的节点压入栈中，然后再将该指针指向下一个节点
    while(pNode != nullptr)  
    {
        nodes.push(pNode);
        pNode = pNode->m_pNext;
    }

    //只要栈不为空，就一直不断的进行下列操作
    while(!nodes.empty())
    {
        pNode = nodes.top();  //pNode永远指向栈顶元素
        printf("%d\t", pNode->m_nValue);
        nodes.pop();  //出栈操作
    }
}

解法3：递归

递归在本质上就是一个栈结构，于是我们又想到了用递归来实现

//要实现反过来输出链表，我们每访问到一个节点的时候，先递归输出它后面的节点，再输出该节点自身，这样链表的输出结果就反过来了
void PrintListReversingly_Recursively(ListNode* pHead)
{
    if(pHead != nullptr)
    {
        if (pHead->m_pNext != nullptr)
        {
            PrintListReversingly_Recursively(pHead->m_pNext);
        }
 
        printf("%d\t", pHead->m_nValue);
    }
}

⭐️递归的代码很简洁，但有一个问题：当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出，显然用栈基于循环实现的代码鲁棒性要好一些

题目2描述：

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：
输入：head = [1,3,2]
输出：[2,3,1]


限制：0 <= 链表长度 <= 10000

解法1：递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {

    vector<int> res;

public:
    //注意:返回值为引用，减少大量内存拷贝
    vector<int>& reversePrint(ListNode* head) {  
        
        //不可以加上条件：head->next == NULL
        if (head == NULL) {
            return res;
        }

        //递归实现
        reversePrint(head -> next);
        res.push_back(head -> val);

        return res;
    }
};

解法2：栈

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {

        stack<int> nodes;  //定义一个栈
        vector<int> res;  //定义一个容器

        ListNode* pNode = head;

        //遍历链表，并把链表的值压入栈中
        while(pNode != NULL) {
            nodes.push(pNode->val);
            pNode = pNode->next;
        }

        //只要栈不为空，就把栈顶元素放入容器
        while(!nodes.empty()) {
            res.push_back(nodes.top());
            nodes.pop();
        }

        return res;
    }
};