Java?詳解如何從尾到頭打印鏈表
更新時間：2022年01月25日 14:35:30 作者：Fly?upward
在我們平時的代碼過程中，鏈表是我們經(jīng)常遇到的一個數(shù)據(jù)結(jié)構(gòu)，它非常的簡單，但Java并不能直接將一個鏈表打印出來，通過這篇文章我們來講解一下這個問題
1.題目
輸入一個鏈表的頭節(jié)點，從尾到頭反過來返回每個節(jié)點的值（用數(shù)組返回）。
題目來源：力扣（LeetCode）
2.解法
2.1棧
棧的特點是先進后出，所以我們創(chuàng)建一個棧，逐個將節(jié)點壓入棧內(nèi)，然后建立一個數(shù)組，將棧內(nèi)的節(jié)點數(shù)值逐個彈出
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack = new Stack<ListNode>();//創(chuàng)建一個棧
ListNode cur = head;
//將節(jié)點壓棧
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
int size = stack.size();//棧的長度
int[] array = new int[size];//創(chuàng)建一個和棧一樣長的數(shù)組
//出棧入數(shù)組
for (int i = 0; i < size; i++) {
array[i] = stack.pop().val;
}
return array;
}
}
2.2遞歸
public class PrintList {
ArrayList<Integer> cur = new ArrayList<Integer>();
public int[] reversePrint(ListNode head) {
recur(head);
int[] array = new int[cur.size()];
for (int i = 0; i <array.length; i++) {
array[i] = cur.get(i);
}
return array;
}
public void recur(ListNode head) {
if(head == null) {
return ;
}
recur(head.next);
cur.add(head.val);
}
}3.復雜度
3.1棧
時間復雜度：O(n)。正向遍歷一遍鏈表，然后從棧彈出全部節(jié)點，等于又反向遍歷一遍鏈表。 空間復雜度：O(n)。額外使用一個棧存儲鏈表中的每個節(jié)點。
3.2遞歸
時間復雜度：O(n) 遍歷鏈表，遞歸 NN次。
空間復雜度：O(n) 系統(tǒng)遞歸需要使用 O(N)的?？臻g
到此這篇關于Java 詳解如何從尾到頭打印鏈表的文章就介紹到這了,更多相關Java 從尾到頭打印鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
JAVA幫助文檔全系列 JDK1.5 JDK1.6 JDK1.7 官方中英完整版整理
JDK(Java Development Kit，Java開發(fā)包，Java開發(fā)工具)是一個寫Java的applet和應用程序的程序開發(fā)環(huán)境。它由一個處于操作系統(tǒng)層之上的運行環(huán)境還有開發(fā)者編譯，調(diào)試和運行用Java語言寫的applet和應用程序所需的工具組成2014-01-01
這篇文章主要介紹了MyBatis連接池的深入和動態(tài)SQL詳解，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-02-02
SpringBoot @Autowired注解注入規(guī)則介紹
這篇文章主要介紹了SpringBoot @Autowired注解注入規(guī)則介紹，具有很好的參考價值，希望對大家有所幫助。2021-11-11
下面小編就為大家?guī)硪黄赗abbitMQ幾種Exchange 模式詳解。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-11-11
Java matches類，Pattern類及matcher類用法示例
這篇文章主要介紹了Java matches類，Pattern類及matcher類用法,結(jié)合實例形式分析了java matches類，Pattern類及matcher類針對字符串常見操作技巧與相關注意事項,需要的朋友可以參考下2019-03-03
這篇文章主要幫助大家理解Java中的靜態(tài)綁定和動態(tài)綁定，在Java中存在兩種綁定方式,一種為靜態(tài)綁定,另一種就是動態(tài)綁定,亦稱為后期綁定,感興趣的小伙伴們可以參考一下2016-02-02
這篇文章主要給大家介紹了關于Java8優(yōu)雅處理集合之Stream的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者使用java8具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2019-03-03
SpringMVC+Mybatis二維碼實現(xiàn)多平臺付款(附源碼)
本文主要實現(xiàn)微信支付寶等支付平臺合多為一的二維碼支付，并且實現(xiàn)有效時間內(nèi)支付有效，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
關于final關鍵字，它也是我們一個經(jīng)常用的關鍵字，可以修飾在類上、或者修飾在變量、方法上，以此看來定義它的一些不可變性！像我們經(jīng)常使用的String類中，它便是final來修飾的類，并且它的字符數(shù)組也是被final所修飾的。但是一些final的一些細節(jié)你真的了解過嗎2022-06-06
這篇文章主要介紹了Lombok和MapStruct整合詳情，文章基于Java的相關資料展開詳細內(nèi)容，需要的小伙伴可以參考一下2022-05-05