劍指offer【6】：從尾到頭打印鏈表

Kahn 發(fā)布于2019-08-16 18:39 / 3112人閱讀

題目

輸入一個(gè)鏈表的頭節(jié)點(diǎn)，從尾到頭反過來打印出每個(gè)節(jié)點(diǎn)的值。

解題思路 一、棧

第一個(gè)遍歷的節(jié)點(diǎn)最后一個(gè)輸出，而最后一個(gè)比遍歷到的節(jié)點(diǎn)第一個(gè)輸出（后進(jìn)先）

    public static ArrayList printListFromTailToHead(ListNode listNode){
        ArrayList list = new ArrayList<>();
        Stack stack = new Stack<>();
        while(listNode != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while(!stack.empty()){
            list.add(stack.pop());
        }
        return list;
    }

二、遞歸（重點(diǎn)理解）

    public ArrayList printListFromTailToHead(ListNode listNode) {
    ArrayList ret = new ArrayList<>();
    if (listNode != null) {
        ret.addAll(printListFromTailToHead(listNode.next));
        ret.add(listNode.val);
    }
    return ret;
}

    public static void test2(ListNode node){
        if(node != null){
            if(node.next != null){
                test2(node.next);
            }
        }
        System.out.println(node.val);
        
    }

總結(jié)

當(dāng)鏈表非常長(zhǎng)時(shí)，常用遞歸的方法會(huì)導(dǎo)致函數(shù)調(diào)用的層級(jí)很深，從而有可能導(dǎo)致函數(shù)調(diào)用棧溢出，顯然用棧基于循環(huán)實(shí)現(xiàn)的代碼魯棒性更好。

云服務(wù)器 GPU云服務(wù)器劍指找不到頭文件 offer webrtc offer

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/75525.html

相關(guān)文章

劍指offer系列——劍指 Offer 06. 從尾到頭打印鏈表（C語言）

摘要：導(dǎo)航小助手劍指從尾到頭打印鏈表題目詳情解題思路源代碼總結(jié)劍指從尾到頭打印鏈表題目詳情輸入一個(gè)鏈表的頭節(jié)點(diǎn)，從尾到頭反過來返回每個(gè)節(jié)點(diǎn)的值用數(shù)組返回。時(shí)間復(fù)雜度方法先反轉(zhuǎn)鏈表并求長(zhǎng)度，在將反轉(zhuǎn)后的鏈表數(shù)據(jù)拷貝至數(shù)組中。 ...

DevTTL 2021-09-04 16:41 評(píng)論0 收藏0
【劍指offer】3.從尾到頭打印鏈表

摘要：題目描述輸入一個(gè)鏈表，按鏈表值從尾到頭的順序返回一個(gè)。最后別忘了，從尾到頭遍歷鏈表，不要忘了將你的結(jié)果進(jìn)行翻轉(zhuǎn)。題目描述輸入一個(gè)鏈表，按鏈表值從尾到頭的順序返回一個(gè)ArrayList。分析要了解鏈表的數(shù)據(jù)結(jié)構(gòu)： val屬性存儲(chǔ)當(dāng)前的值，next屬性存儲(chǔ)下一個(gè)節(jié)點(diǎn)的引用。要遍歷鏈表就是不斷找到當(dāng)前節(jié)點(diǎn)的next節(jié)點(diǎn)，當(dāng)next節(jié)點(diǎn)是null時(shí)，說明是最后一個(gè)節(jié)點(diǎn)，停止遍歷。最...

graf 2019-08-23 14:37 評(píng)論0 收藏0
#yyds干貨盤點(diǎn)#劍指 Offer 06. 從尾到頭打印鏈表

摘要：題目輸入一個(gè)鏈表的頭節(jié)點(diǎn)，從尾到頭反過來返回每個(gè)節(jié)點(diǎn)的值用數(shù)組返回。題目輸入一個(gè)鏈表的頭節(jié)點(diǎn)，從尾到頭反過來返回每個(gè)節(jié)點(diǎn)的值（用數(shù)組返回）。示例 1：輸入：head = [1,3,2]輸出：[2,3,1]限制：0

SQC 2021-11-23 09:51 評(píng)論0 收藏0
劍指Offer(Java版) 持續(xù)更新中

摘要：面試題從尾到頭打印鏈表輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值面試題重建二叉樹輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。隊(duì)列中的元素為類型。其中負(fù)數(shù)用補(bǔ)碼表示。面試題2 單例(之前有整理，略) 面試題3 二維數(shù)組中的查找 public boolean find(int target, int [][] arra...

justCoding 2019-08-15 11:04 評(píng)論0 收藏0
利用PHP實(shí)現(xiàn)《劍指 offer》之鏈表（數(shù)據(jù)結(jié)構(gòu)與算法實(shí)戰(zhàn) ）

摘要：一定要認(rèn)真看分析注釋題目要求題目描述輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。分析因?yàn)殒湵碇挥兄喇?dāng)前結(jié)點(diǎn)才能知道下一結(jié)點(diǎn)，所以不可能直接從后往前打印。一定要認(rèn)真看分析 | 注釋 | 題目要求 Question 1 題目描述：輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。分析：因?yàn)殒湵碇挥兄喇?dāng)前結(jié)點(diǎn)才能知道下一結(jié)點(diǎn)，所以不可能直接從后往前打印。這種逆序的算法（策略）我們常用棧這...

hiYoHoo 2019-06-28 18:48 評(píng)論0 收藏0