剑指Offer - 从尾到头打印链表

题目描述

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

接口

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

    }
};

解答

使用 std::stack

栈是先进后出的一种数据结构，很符合本题要求从尾到头逆序输出，因此可以使用 std::stack 先将链表所有的值从头节点到尾节点的顺序压入栈中，然后将栈顶元素推入 vector 中再将栈顶元素出栈，重复操作直到栈为空。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> array;
        if (head == nullptr) return array;
        stack<int> stk;
        while (head != nullptr) {
            stk.push(head->val);
            head = head->next;
        }
        while (stk.empty() != false) {
            array.push_back(stk.top());
            stk.pop();
        }
        return array;
    }
};

逆序链表

在这一题中，可以先将链表逆序，再将逆序的链表的值推入 vector 中。对已经构建好的链表而言，逆序链表的关键在于从原链表第二个节点开始将每一个节点的 next 指针指向其原链表中的前一节点，原本的头节点的 next 指针指向 nullptr。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> array;
        if (head == nullptr) return array;
        if (head->next == nullptr) return vector<int>(1, head->val);
        ListNode *latter = head->next, *temp = nullptr;
        head->next = nullptr;
        while (latter != nullptr) {
            temp = latter->next;
            latter->next = head;
            head = latter;
            latter = temp;
        }
        while (head != nullptr) {
            array.push_back(head->val);
            head = head->next;
        }
        return array;
    }
};

递归方法

递归的思路是：假如当前节点指向的下一节点不为空，则先将下一节点加入 vector 中，再将当前节点加入 vector 中。故而会一直递归到尾节点，第一个加入 vector 的将是尾节点，再一层层往上从而达到逆序将链表节点的值加入到 vector 中。

这里要注意的点是递归函数处，vector 必须使用引用传递，否则通过值传递得到的 vector 结果将是空的 vector。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> array;
        if (head == nullptr) return array;
        recursePushBack(array, head);
        return array;
    }
    
    void recursePushBack(vector<int> &array, ListNode *node) {
        if (node->next != nullptr)
            recursePushBack(array, node->next);
        array.push_back(node->val);
        return;
    }
};