从尾到头打印链表java版(栈思路、数组翻转和递归思路)

admin 2020-04-08 15:56:19 java常见问答 5292

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

下面提供三种思路三种答案,第一就是利用栈先入后出的特性完成,第二就是存下来然后进行数组翻转。

第三是利用递归。

思路一:栈思路

class Solution
{
    public:
        vector < int > printListFromTailToHead(ListNode * head)
        {
            vector < int > value;
            ListNode * p = NULL;
            p = head;
            stack < int > stk;
            while (p != NULL)
            {
                stk.push(p - > val);
                p = p - > next;
            }
            while (!stk.empty())
            {
                value.push_back(stk.top());
                stk.pop();
            }
            return value;
        }
};

思路二:数组翻转:数组翻转可以用C++自带的函数,也可以自己实现

class Solution
{
    public:
        vector < int > printListFromTailToHead(ListNode * head)
        {
            vector < int > value;
            ListNode * p = NULL;
            p = head;
            while (p != NULL)
            {
                value.push_back(p - > val);
                p = p - > next;
            }
            //reverse(value.begin(),value.end()); //C++自带的翻转函数
            int temp = 0;
            int i = 0, j = value.size() - 1;
            while (i < j)
            {
                temp = value[i]; //也可以用swap函数,swap(value[i],value[j]);
                value[i] = value[j];
                value[j] = temp;
                i++;
                j--;
            }
            return value;
        }
};

思路三:递归思路:

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