漫画：美团面试题，链表逆序存数组
The following article is from 小夕学算法 Author 小夕
面试现场
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
借助栈来实现
为了方便理解递归，我们先采取栈的方式去实现一下。比如对于下图中所示的链表需要把它们逆序保存到数组中，本来正常顺序是1,2,3，要逆序到数组，自然想到了栈这种后进先出的数据结构。
从前往后遍历链表，1、2、3依次进入到栈里面。
借助栈的动画
借助栈的实现代码
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack=new Stack<Integer>();
while(listNode!=null){
stack.push(listNode.val); //进栈
listNode=listNode.next;
}
ArrayList<Integer> list=new ArrayList<Integer>();
while(!stack.isEmpty()){//出栈进数组
list.add(stack.pop());
}
return list;
}
}
借助栈的复杂度分析
由于遍历了一次链表+遍历了一次栈，所以时间复杂度是O(2n),新建了一个栈和要返回的数组，空间复杂度是O(2n).这里为什么要用2n，是为了和递归的实现来进行对比。
递归实现
Java
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.*;
public class Solution {
ArrayList<Integer> list = new ArrayList();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode!=null){
printListFromTailToHead(listNode.next);
list.add(listNode.val);
}
return list;
}
}
Php
<?php
/*class ListNode{
var $val;
var $next = NULL;
function __construct($x){
$this->val = $x;
}
}*/
$resultarray = array();
function printListFromTailToHead($head)
{
if($head == NULL)
return [];
// write code here
if($head != NULL){
$resultarray = printListFromTailToHead($head->next);
array_push($resultarray,$head->val);
}
return $resultarray;
}
Python
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
if(listNode is None):
return []
if(listNode is not None):
self.resultList = self.printListFromTailToHead(listNode.next)
self.resultList.append(listNode.val)
return self.resultList
JS
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function printListFromTailToHead(head) {
if(head == null)
return []
// write code here
if(head != null){
res = printListFromTailToHead(head.next);
res.push(head.val);
}
return res;
}
C++
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> value;
vector<int> printListFromTailToHead(ListNode* head) {
ListNode *p=NULL;
p=head;
if(p!=NULL){
if(p!=NULL){
printListFromTailToHead(p->next);
value.push_back(p->val);
}
}
return value;
}
};
递归的实现，我先把代码写出来，我一行行分析一下代码，给你说一下递归的实现。五种代码的实现逻辑完全相同。代码风格也保持的非常一致，以下例子对照对应的代码进行理解即可。在下面的所有图里面，红色标注的代码代表正在执行了，黑色标注的代码未执行。
可以看到正在执行节点为1的 printListFromTailToHead(listNode.next);，
由于调用了自身函数printListFromTailToHead，所以 list.add(listNode.val);
还未执行到，进入到**节点为2**的执行逻辑代码。
递归的动画
絮叨
小夕一开始不知道以什么方式讲解递归，emmm...后来想了一会觉得按照代码执行过程然后去绘制每一张图还挺不错的。另外大家看到讲解中示例图中是Java代码实现，其它语言的递归大家自行替换为自己的语言理解即可，小夕知道其它语言的朋友可能看Java稍微有那么一丢丢的困难，为此小夕的五种语言实现上大家可以看到是完全一样的，所以语言没用过不重要，丝毫不影响你的理解，小夕也是花心思的了呀~
原创不易，觉得文章不错的不妨点赞（右下角在看）、转发、留言三连支持一下小夕呀~你的在看和转发就是小夕原创的不竭的动力。
识别关注我们
了解更多精彩内容
点分享
点点赞
点在看