题目描述

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

样例

输入

1->2->3

输出

3->2->1

算法1

(直接) $O(n)$

先从前往后遍历一遍输入的链表，
将结果记录在答案数组中。
最后再将得到的答案数组逆序返回即可。

C++ 代码

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        while(head)
        {
            res.push_back(head->val);
            head = head->next;
        }
        return vector<int>(res.rbegin(), res.rend());
    }
};

算法2

如果要求返回的是链表，则步骤如下。

1. 保存当前头结点的下一个结点。
2. 将当前头结点的下一个结点设指向“上一个结点”，此时就是翻转。
3. 将当前头结点设置“上一个节点”。
4. 将保存的下一个结点设置为头结点。

C++ 代码

public ListNode reverseList(ListNode head) {
    ListNode next = null;
    ListNode pre = null

    while (head != null) {
        next = head.next; //将head.next赋值给next变量，也就是说next指向了节点2，先将节点2保存起来。
        head.next = pre;//将pre变量赋值给了head.next，即节点1指向了null。
        pre = head; //将head赋值给了pre，即pre指向节点1，将节点1设为“上一个节点”。
        head = next; // 将next赋值给head，即head指向了节点2。将节点2设置为“头结点”。
    }
    return pre;
}