JZ3 题解 | #从尾到头打印链表#

思路分析

• 给出一个链表，需要我们从尾部到头部打印出这个链表的所有的节点的权值。

思路分析

解法一 直接遍历

• 题目很简单，很朴素。我们直接从这个链表的头节点开始进行遍历。然后我们记录下这个数组的每个节点的信息。最后反转一下整个数组，返回即可。

• 代码如下

  • 需要直接遍历长度为n的链表的所有的结点，时间复杂度为O(n）
  • 需要存储长度为n的链表的所有的结点，空间复杂度为O(n)

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ans;
          // 从头节点开始进行遍历
        while(head){
            // 将每个节点的权值放入动态数组里面
            ans.push_back(head->val);
            // 指针后移动
            head=head->next;
        }
        // 反转整个数组
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

解法二 递归写法

• 由于这个题目需要我们从后面向前面开始打印这个数组。所以我们可以对遍历的结点进行一个递归，我们先递归到这个链表的最后面，然后不断向前收集权值。

• 代码如下

  • 用DFS同样会遍历所有的结点，时间复杂度为O(n）
  • 需要存储长度为n的链表的所有的结点，空间复杂度为O(n)

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> ans;
    void dfs(ListNode* now){
        // 递归的出口为当前的指针为空的情况
        if(!now){
            return;
        }
        // 向后面进行递归
        dfs(now->next);
        // 递归之后收集权值
        ans.push_back(now->val);
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        dfs(head);
        return ans;
    }
};