剑指offer6:逆向打印链表

本站访问次数:

问题描述:输入一个链表的头节点,反向打印出链表. 链表结构如下

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x):
        val(x), next(NULL){
    } 
};

思路:链表反向打印,先进后出,考虑使用栈.

class Solution {
public:
    void printListFromTailToHead(ListNode* head) {
        if(head==nullptr){
            return ;
        }
        ListNode* p = head;
        stack<int> sta;
        while(p!=nullptr){
            sta.push(p->val);
            p = p->next;
        }
        while(!sta.empty()){
            cout<<sta.top()<<endl;
            sta.pop()
        }
    }
};

对于以上用栈实现的代码,可以联想到递归.

class Solution {
public:
    void printListFromTailToHead(ListNode* head) {
        if(head!=nullptr){
            printListFromTailToHead(head->next);
            cout<<head->val<<endl;
        }
    }
};

递归代码相比循环更加简洁,但是若递归栈太深,会造成内存溢出.递归和循环优先使用循环