面試現場

輸入一個鏈表，按鏈表從尾到頭的順序返回一個ArrayList。

藉助棧來實現

爲了方便理解遞歸，我們先採取棧的方式去實現一下。比如對於下圖中所示的鏈表需要把它們逆序保存到數組中，本來正常順序是 1,2,3，要逆序到數組，自然想到了棧這種後進先出的數據結構。

從前往後遍歷鏈表，1、2、3 依次進入到棧裏面。可以看到棧裏面出棧的順序是 3、2、1，所以新建一個數組，然後依次出棧的每個元素依次添加到數組中，就是我們最終得到的結果。以下是出棧進數組的過程：

藉助棧的動畫

藉助棧的實現代碼

/**
*    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**的執行邏輯代碼。

同理緊接着進入到節點爲 3 的 printListFromTailToHead(listNode.next); 執行代碼。

執行到這裏的時候，由於節點 3 是鏈表末尾，終於在這裏解開了遞歸這個無底洞~，緊接着就一層層出棧並添加到數組。

遞歸的動畫

絮叨

小夕一開始不知道以什麼方式講解遞歸，emmm... 後來想了一會覺得按照代碼執行過程然後去繪製每一張圖還挺不錯的。另外大家看到講解中示例圖中是 Java 代碼實現，其它語言的遞歸大家自行替換爲自己的語言理解即可，小夕知道其它語言的朋友可能看 Java 稍微有那麼一丟丟的困難，爲此小夕的五種語言實現上大家可以看到是完全一樣的，所以語言沒用過不重要，絲毫不影響你的理解，小夕也是花心思的了呀~

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/btPiupLgVgdiVUnR2CDFLA