leetcode|剑指offter|面试题6：从尾到头打印链表

面试题06. 从尾到头打印链表

问题描述

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

示例

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

我们很自然地可以想到把链表中链接节点的指针反转过来，改变链表的方向，然后就可以从头到尾输出了。但是这种方法会改变原来的链表结构，如果要求不修改链表的结构可以有以下方法：

解法一：
遍历链表的顺序是从头到尾，但是题目要求输出的顺序却是从尾到头，第一个遍历到的节点最后一个输出，而最后一个遍历到的节点第一个输出。是典型的”后进先出”，栈这种数据结构具有该特点，我们可以在从头到尾遍历的时候，把经过的每个节点放入栈中，遍历完后，再从栈的顶端开始逐个输出节点的值。

leetcode解答：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> result;
    vector<int> reversePrint(ListNode* head) {
         stack<int>s ;
         while(head)
         {
             s.push(head->val);//循环遍历，入栈
             head=head->next;
         }
         while(!s.empty())
         {
            result.push_back(s.top()); //出栈
            s.pop();
         }
         return result;
    }
};

解法二：
递归在本质上就是一个栈结构，可以用递归来实现。当访问到每个节点的时候，先递归输出它后面的节点，再输出该节点，最后链表的输出结果就反过来了。

leetcode解答：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> result;//输出
    vector<int> reversePrint(ListNode* head) {
        if(head==nullptr)
        return result;
        reversePrint(head->next); //递归
        result.push_back(head->val);
        return result;
    }
};

解法三：改变链表的结构
直接翻转指针。

初始状态，pre是NULL，head指向当前的头节点A，next指向A节点的下一个节点B。首先从A节点开始逆序，将A节点的next指针指向pre，因为pre的当前值是NULL，所以A节点就从链表中脱离出来了，然后移动head和next指针，使它们分别指向B节点和B的下一个节点C（因为当前的next已经指向B节点了，因此修改A节点的next指针不会导致链表丢失）。逆向节点A之后，链表的状态如图下图所示：

经过一轮迭代：

再经过一轮迭代：

可以看出再经过一轮就可以完成链表的逆序排序，循环的终止条件为head为空NULL

链表的状态图 参考:单链表的逆序
leetcode解答:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> result;
    vector<int> reversePrint(ListNode* head) {
        ListNode *next;
        ListNode *pre=nullptr;
        while(head)
        {
            next=head->next ;//保存当前节点的下一节点
            head->next=pre;//当前节点指向前一个节点，反向改变指针。
            pre=head;//更新前一个节点
            head=next;//更新当前节点
        }
        while(pre){//上一个while循环结束后，pre指向新的链表头
            result.push_back(pre->val);
            pre = pre->next;
        }
        return result;
        
    }
};