Java?詳解如何從尾到頭打印鏈表

更新時(shí)間：2022年01月25日 14:35:30 作者：Fly?upward

在我們平時(shí)的代碼過程中，鏈表是我們經(jīng)常遇到的一個(gè)數(shù)據(jù)結(jié)構(gòu)，它非常的簡單，但Java并不能直接將一個(gè)鏈表打印出來，通過這篇文章我們來講解一下這個(gè)問題

1.題目

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

題目來源：力扣（LeetCode）

2.解法

2.1棧

棧的特點(diǎn)是先進(jìn)后出，所以我們創(chuàng)建一個(gè)棧，逐個(gè)將節(jié)點(diǎn)壓入棧內(nèi)，然后建立一個(gè)數(shù)組，將棧內(nèi)的節(jié)點(diǎn)數(shù)值逐個(gè)彈出

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();//創(chuàng)建一個(gè)棧
        ListNode cur = head;
        //將節(jié)點(diǎn)壓棧
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        int size = stack.size();//棧的長度
        int[] array = new int[size];//創(chuàng)建一個(gè)和棧一樣長的數(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.復(fù)雜度

3.1棧

時(shí)間復(fù)雜度：O(n)。正向遍歷一遍鏈表，然后從棧彈出全部節(jié)點(diǎn)，等于又反向遍歷一遍鏈表。空間復(fù)雜度：O(n)。額外使用一個(gè)棧存儲(chǔ)鏈表中的每個(gè)節(jié)點(diǎn)。

3.2遞歸

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

空間復(fù)雜度：O(n) 系統(tǒng)遞歸需要使用 O(N)的棧空間

到此這篇關(guān)于Java 詳解如何從尾到頭打印鏈表的文章就介紹到這了,更多相關(guān)Java 從尾到頭打印鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

相關(guān)文章

JAVA幫助文檔全系列 JDK1.5 JDK1.6 JDK1.7 官方中英完整版整理
JDK(Java Development Kit，Java開發(fā)包，Java開發(fā)工具)是一個(gè)寫Java的applet和應(yīng)用程序的程序開發(fā)環(huán)境。它由一個(gè)處于操作系統(tǒng)層之上的運(yùn)行環(huán)境還有開發(fā)者編譯，調(diào)試和運(yùn)行用Java語言寫的applet和應(yīng)用程序所需的工具組成
2014-01-01
MyBatis連接池的深入和動(dòng)態(tài)SQL詳解
這篇文章主要介紹了MyBatis連接池的深入和動(dòng)態(tài)SQL詳解，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2022-02-02
SpringBoot @Autowired注解注入規(guī)則介紹
這篇文章主要介紹了SpringBoot @Autowired注解注入規(guī)則介紹，具有很好的參考價(jià)值，希望對大家有所幫助。
2021-11-11
基于RabbitMQ幾種Exchange 模式詳解
下面小編就為大家?guī)硪黄赗abbitMQ幾種Exchange 模式詳解。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧
2017-11-11
Java matches類，Pattern類及matcher類用法示例
這篇文章主要介紹了Java matches類，Pattern類及matcher類用法,結(jié)合實(shí)例形式分析了java matches類，Pattern類及matcher類針對字符串常見操作技巧與相關(guān)注意事項(xiàng),需要的朋友可以參考下
2019-03-03
理解Java中的靜態(tài)綁定和動(dòng)態(tài)綁定
這篇文章主要幫助大家理解Java中的靜態(tài)綁定和動(dòng)態(tài)綁定，在Java中存在兩種綁定方式,一種為靜態(tài)綁定,另一種就是動(dòng)態(tài)綁定,亦稱為后期綁定,感興趣的小伙伴們可以參考一下
2016-02-02
Java8處理集合的優(yōu)雅姿勢之Stream
這篇文章主要給大家介紹了關(guān)于Java8優(yōu)雅處理集合之Stream的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者使用java8具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧
2019-03-03
SpringMVC+Mybatis二維碼實(shí)現(xiàn)多平臺(tái)付款(附源碼)
本文主要實(shí)現(xiàn)微信支付寶等支付平臺(tái)合多為一的二維碼支付，并且實(shí)現(xiàn)有效時(shí)間內(nèi)支付有效，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2021-08-08
Java超詳細(xì)分析講解final關(guān)鍵字的用法
關(guān)于final關(guān)鍵字，它也是我們一個(gè)經(jīng)常用的關(guān)鍵字，可以修飾在類上、或者修飾在變量、方法上，以此看來定義它的一些不可變性！像我們經(jīng)常使用的String類中，它便是final來修飾的類，并且它的字符數(shù)組也是被final所修飾的。但是一些final的一些細(xì)節(jié)你真的了解過嗎
2022-06-06
Lombok和MapStruct整合詳情
這篇文章主要介紹了Lombok和MapStruct整合詳情，文章基于Java的相關(guān)資料展開詳細(xì)內(nèi)容，需要的小伙伴可以參考一下
2022-05-05