首页 > 代码库 > 从尾到头打印链表

从尾到头打印链表

  • 题目描述:

输入一个链表的头结点,从尾到头打印链表每个节点的值。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
  • 分析:

反向打印链表,有两种思路:

  1.    既然是要打印,肯定要遍历链表。而打印一般理解为只读操作,并不对链表进行修改,也不改变链表结构。但是链表的遍历我们都知道只能是是从头到尾的,但是输出去要求从尾到头,也就是说第一个遍历到的最后输出,而最后一个遍历到的第一个输出。这个思想复合典型的 “后进先出”,也就是说我们可以借用一个栈来实现这种反向打印的操作。
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        stack<ListNode*> NodeStack;
        
        ListNode* pHead = head;
        while(pHead != NULL){
            NodeStack.push(pHead);
            pHead = pHead->next;
        }
        
        vector<int> vals;
        while(!NodeStack.empty()){
            vals.push_back(NodeStack.top()->val);
            NodeStack.pop();
        }
        return vals;
    }
};
  1. 不考虑不改变列表结构这一条件,要反向输出,只要把链表整个反转过来再输出就好了。即把头结点变成尾节点,而尾变成头。这种方法在反转链表中再进行总结。

从尾到头打印链表