欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間：2022年01月25日 14:35:30   作者：Fly?upward  
在我們平時(shí)的代碼過程中，鏈表是我們經(jīng)常遇到的一個(gè)數(shù)據(jù)結(jié)構(gòu)，它非常的簡(jiǎn)單，但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();//棧的長(zhǎng)度
        int[] array = new int[size];//創(chuàng)建一個(gè)和棧一樣長(zhǎ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.復(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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評(píng)論