剑指 Offer 06. 从尾到头打印链表

• 注意C++中类和结构体定义要按引用顺序，而C#不用，会预先扫一遍。
• 扫一遍存下来链表元素倒序输出可以，用回溯和栈来解决也可以，时间空间复杂度都是O(n)，但回溯和栈的思想更加适合倒序这种问题，注意。
• 注意一下C++的main函数调用Soultion用的是非new的实例化方式。

A a;  // a存在栈上 使用完后不需要手动释放，该类析构函数会自动执行，局部变量，比如此题main函数生成一个局部的Solution对象调用里面的方法。
a.doit();
A* a = new a();  // a存在堆中 只有调用到delete时再会执行析构函数，如果程序退出而没有执行delete则会造成内存泄漏，全局变量，比如链表，就需要全局调用。C#有GC可以随便new
a->doit();

//C++

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

class Solution {
public:
    vector<int> res;
    vector<int> reversePrint(ListNode* head) {
        doit(head);
        return res;
    }

    void doit(ListNode* head) {
        if (head == nullptr) {
            return;
        }
        doit(head->next);
        res.push_back(head->val);
    }
};


int main() {
    ListNode* head = new ListNode(1);// 有new
    ListNode* a1 = new ListNode(3);
    ListNode* a2 = new ListNode(2);
    head->next = a1;
    a1->next = a2;
    Solution res; //无new
    vector<int> ans = res.reversePrint(head);
    for (int item : ans) {
        cout << item << " ";
    }
    system("pause");
    return 0;
}
//C# 回溯
class Test03 {
    static void Main(string[] args) {
        ListNode head = new ListNode(1);
        ListNode a1 = new ListNode(2);
        ListNode a2 = new ListNode(3);
        head.next = a1;
        a1.next = a2;
        int[] ans = new Solution().ReversePrint(head);
        foreach (int i in ans) {
            Console.WriteLine(i);
        }
    }
}

class Solution {
    List<int> res = new List<int>();
    public int[] ReversePrint(ListNode head) {
        doit(head);
        return res.ToArray();
    }

    void doit(ListNode head) {
        if (head == null) {
            return;
        }
        doit(head.next);
        res.Add(head.val);
    }
}

class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

这次放的全一点，ListNode和输入类都放了做范例，以后只放Solution。