题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

初始代码

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {

    }
};

解法1

思路: 使用头插法得到一个新链表, 该链表中的元素顺序正好和原链表相反. 随后通过遍历新链表, 生成一个vector并返回.

这是我首先想到的方法. 因为对链表的头插法印象比较深刻. 所以最先想到通过头插法来实现链表元素顺序的逆转. 也考虑过另外开辟一个链表的内存会使得该解法的空间复杂度达到O(n). 但毕竟是第一个解法, 先保证正确性再说, 后续在考虑优化.

由于这一解法使用new运算符分配了新链表各个阶段的空间. 因此, 在函数返回之前, 要记得释放掉新链表的结点空间. 好在本身生成vector就需要遍历一次新链表, 在这个遍历的过程中, 顺便也就释放了内存. 就很自然 :)

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode* head_new = NULL;
        for(ListNode *p = head; p != NULL; p = p->next)
        {
            ListNode *q = new ListNode(p->val);
            q->next = head_new;
            head_new = q;
        }

        vector<int> res;
        for(ListNode *p = head_new; p != NULL;)
        {
            res.push_back(p->val);
            ListNode *q = p->next;
            delete p; //释放空间
            p = q;
        }

        return res;
    }
};

解法2

解法2在解法1的基础上, 进行优化. 参考了其它人的优秀解题思路, 发现可以在链表内部就完成反转工作, 没必要另外开辟空间. 其实根本的思想和"头插法"是一脉相承的. 在遍历一次原链表的过程中, 通过修改指针域来边遍历边翻转. 稍微的难点是要理解清楚每一次指针域赋值的含义, 它们执行的先后顺序不能随意变更.

Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode *pre, *tmp, *cur;
        pre = NULL;
        cur = head;
        while(cur)
        {
            tmp = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = tmp;
        }

        vector<int> res;
        while(pre){
            res.push_back(pre->val);
            pre = pre -> next;
        }

        return res;
    }
};

解法3

同样是参考了题解区的置顶题解, 对这个简单的题目再进行多维的解决, 从而达到"做一题等于做多题"的效果.

本解法采用递归来实现链表的反转. 其实递归和反转可以说是一对孪生兄弟, 递归在触底反弹之后, 执行的就是一个逆向的遍历过程.

关于本题使用递归, 有两种方式声明vector<int> ret变量. </int>

  • 在函数内部声明. 从而在每一层递归都需要声明一次该变量. 一定程度上会加大内存消耗.
  • 在函数外部声明, 即把ret声明为Solution类的一个公有变量. 从而函数每次直接调用ret执行操作即可, 不需要在每一层递归都声明一个新的ret.

下面分别是两种实现的代码:

在函数内部声明ret

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ret;
        if(!head) return ret;
        ret = printListFromTailToHead(head->next);
        ret.push_back(head->val);
        return ret;
    }
};

在函数外部将ret声明为Solution类的public成员变量

class Solution {
public:
    vector<int> ret;
    vector<int> printListFromTailToHead(ListNode* head) {
        if(!head) return ret;
        printListFromTailToHead(head->next);
        ret.push_back(head->val);
        return ret;
    }
};

解法4

解法4是直接利用std命名空间内的reverse()方法来实现vector内部元素的翻转. 虽然说这种直接调用库函数的方法显得很不"道德". 但单看效果, 这确实不失为一种办法.

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ret;
        ListNode *p = head;
        while(p){
            ret.push_back(p->val);
            p = p->next;
        }
        std::reverse(ret.begin(), ret.end());
        return ret;
    }
};