【剑指offer】面试题06 - 从尾到头打印链表

た入场券 2022-11-03 11:54 64阅读 0赞

### 文章目录 ###

*  面试题 6：从尾到头打印链表
 *   *  解法一：使用栈数据结构
     *  解法二：辅助数组
     *  解法三：递归打印

# 面试题 6：从尾到头打印链表 #

题目描述

> 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
> 
> 题目链接：[LeetCode][] [牛客网][Link 1]

## 解法一：使用栈数据结构 ##

> 思路：
> 
> 1.  开一个STL中的栈数据结构
> 2.  从头开始遍历将链表节点入栈
> 3.  边出栈边将值保存进入 vector 数组中

vector<int> printListFromTailToHead(ListNode* head) { 
        int count = 0;
        ListNode* node = head;
        stack<int> s;
        while(node)
        { 
            s.push(node->val);
            node = node->next;
            count++;
        }
        vector<int> v;
        while(!s.empty())
        { 
            v.push_back(s.top());
            s.pop();
        }
        return v;
    }

## 解法二：辅助数组 ##

> 思路：
> 
> 1.  遍历链表，数一数一共有多少个结点，记作 nums
> 2.  开一个 nums 大小的 vector 数组
> 3.  从头遍历链表，将值倒序填入 vector 数组中

vector<int> printListFromTailToHead(ListNode* head) { 
        int nums = 0;
        ListNode* temp = head;
        while(temp)
        { 
            nums++;
            temp = temp->next;
        }
        temp = head;
        vector<int> v(nums);
        for(int i = nums - 1; i >= 0; i--)
        { 
            v[i] = temp->val;
            temp = temp->next;
        }
        return v;
    }

## 解法三：递归打印 ##

> 思路：
> 
> 1.  递归到NULL节点，开始从后往前保存进入 vector 数组中

void _rec(vector<int>& v, ListNode* node)
    { 
        if(node == nullptr)
            return;
        _rec(v, node->next);
        v.push_back(node->val);
    }
    vector<int> printListFromTailToHead(ListNode* head) { 
        vector<int> v;
        ListNode* node = head;
        _rec(v,node);
        return v;
    }

[LeetCode]: https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
[Link 1]: https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey