輸入一個(gè)鏈表的頭節(jié)點(diǎn)，從尾到頭反過(guò)來(lái)返回每個(gè)節(jié)點(diǎn)的值（用數(shù)組返回）。

示例

輸入：head = [1,3,2]

輸出：[2,3,1]

限制：0 <= 鏈表長(zhǎng)度 <= 10000

方法一：棧

棧的特點(diǎn)是后進(jìn)先出，即最后壓入棧的元素最先彈出?？紤]到棧的這一特點(diǎn)，使用棧將鏈表元素順序倒置。從鏈表的頭節(jié)點(diǎn)開(kāi)始，依次將每個(gè)節(jié)點(diǎn)壓入棧內(nèi)，然后依次彈出棧內(nèi)的元素并存儲(chǔ)到數(shù)組中。

• 創(chuàng)建一個(gè)棧，用于存儲(chǔ)鏈表的節(jié)點(diǎn)

• 創(chuàng)建一個(gè)指針，初始時(shí)指向鏈表的頭節(jié)點(diǎn)

• 當(dāng)指針指向的元素非空時(shí)，將指針指向的節(jié)點(diǎn)放入到棧中，并且將指針指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)

• 獲取棧的大小，并且創(chuàng)建一個(gè)數(shù)組，其大小為 是棧的大小

• 循環(huán)遍歷從棧內(nèi)彈出一個(gè)節(jié)點(diǎn)，并且將節(jié)點(diǎn)的值存到數(shù)組中

• 最后返回結(jié)果

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)。正向遍歷一遍鏈表，然后從棧彈出全部節(jié)點(diǎn)，等于又反向遍歷一遍鏈表。

• 空間復(fù)雜度：O(n)。額外使用一個(gè)棧存儲(chǔ)鏈表中的每個(gè)節(jié)點(diǎn)。

方法二：遞歸法

先走至鏈表末端，回溯時(shí)依次將節(jié)點(diǎn)值加入列表 ，這樣就可以實(shí)現(xiàn)鏈表值的倒序輸出。

• 遞推階段：每次傳入 head.next ，以 head == null（即走過(guò)鏈表尾部節(jié)點(diǎn)）為遞歸終止條件，此時(shí)直接返回。

• 回溯階段： 層層回溯時(shí)，將當(dāng)前節(jié)點(diǎn)值加入列表，即tmp.add(head.val)。

• 最終，將列表 tmp 轉(zhuǎn)化為數(shù)組 res ，并返回即可。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度 O(N)： 遍歷鏈表，遞歸 N 次。

• 空間復(fù)雜度 O(N)： 系統(tǒng)遞歸需要使用 O(N) 的?？臻g。

寫(xiě)在最后

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。