[[377395]]

前言

今天繼續(xù)算法題：從尾到頭打印鏈表

鏈表

在看今天題目之前，我們先了解下鏈表。

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)。由于不必須按順序存儲，鏈表的插入和刪除操作可以達到O(1)的復(fù)雜度

熟悉數(shù)組的都知道，數(shù)組是需要一塊連續(xù)的內(nèi)存空間來存儲。而鏈表就不需要，它是通過指針來將內(nèi)存塊串聯(lián)起來。

常見的鏈表結(jié)構(gòu)有：單鏈表、雙向鏈表和循環(huán)鏈表。(圖片來自參考鏈接)

單鏈表

第一個接點為頭結(jié)點，最后一個結(jié)點是尾結(jié)點。

從圖中可以看出來：當(dāng)某個結(jié)點不是指向下一個結(jié)點，而是指向了null，空地址，那么這個結(jié)點就是這個鏈表最后一個結(jié)點，也就是尾結(jié)點。

當(dāng)我們插入或者刪除結(jié)點只需要修改next結(jié)點就行，也就是修改next指針指向地址，比如這樣一個鏈表：

a->next=b, b->next=c, c->next=d 

a下一個結(jié)點是b，b下一個結(jié)點是c...

如果我們要在ab直接插入一個結(jié)點p，得益于鏈表的不連續(xù)性，我們只需要修改a的next為p，p的next為b就行了。

a->next=p, p->next=b, b->next=c, c->next=d 

通俗點說，插入的時候，就修改兩個結(jié)點的跟屁蟲就行啦。所以不同于數(shù)組插入和刪除操作，鏈表的插入和刪除效率很高，不需要考慮空間連續(xù)問題，所以對應(yīng)的時間復(fù)雜度是O(1)。

但是反過來，如果要查詢第n個數(shù)據(jù)為誰，這個就比較麻煩了。不像數(shù)組由于內(nèi)存連續(xù)，所以很輕易就知道n對應(yīng)的數(shù)據(jù)。而鏈表需要一個個next查找，所以鏈表隨機訪問的效率就不如數(shù)組了，時間復(fù)雜度為O(n)。

循環(huán)鏈表

循環(huán)鏈表和單鏈表的區(qū)別就是，尾結(jié)點指針會指向頭結(jié)點，形成一個環(huán)形，這就是循環(huán)鏈表。

雙向鏈表

如圖所示，雙向鏈表和單鏈表的區(qū)別就是，每個結(jié)點不僅有下個結(jié)點的地址，還有上一個結(jié)點的地址。

這樣有什么好處呢?在特定的情境中能提高效率。比如我要在某個結(jié)點B的前面插入數(shù)據(jù)，那么我需要從頭開始便利，找到某個結(jié)點的next指向這個B的地址，然后進行數(shù)據(jù)的插入。

但是雙向鏈表則可以直接獲知結(jié)點B的前驅(qū)結(jié)點地址，大大提高了插入效率。

鏈表的基礎(chǔ)知識就介紹到這里了，下面看一個鏈表相關(guān)的算法題。

題目：從尾到頭打印鏈表

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

示例 1：

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

限制：

0 <= 鏈表長度 <= 10000

解法一

題目意思很簡單，就是一個鏈表，現(xiàn)在要先從尾巴倒著打印鏈表的數(shù)字。

那我們就可以想到可以用到遞歸算法，遞歸算法其實就是兩步，先遞后歸，我們可以先傳遞到鏈表的最后一位，也就是next->null為空的時候，然后開始?xì)w檔把數(shù)據(jù)依次輸出，即完成了從結(jié)尾開始輸出數(shù)字的需求了。

• 遞推階段：走到鏈表結(jié)尾為結(jié)束的標(biāo)志。
• 歸檔階段：從結(jié)尾處一層層輸出數(shù)字，先輸出到ArrayList，在轉(zhuǎn)為數(shù)組。

不明白的可以看看代碼：

class Solution { 
    ArrayList<Integer> tmp = new ArrayList<Integer>(); 
    public int[] reversePrint(ListNode head) { 
        recur(head); 
        int[] res = new int[tmp.size()]; 
        for(int i = 0; i < res.length; i++) 
            res[i] = tmp.get(i); 
        return res; 
    } 
 
    //遞歸方法 
    void recur(ListNode head) { 
     //到鏈表結(jié)尾處，遞推結(jié)束，開始?xì)w檔，依次輸出 
        if(head == null) return; 
        recur(head.next); 
        tmp.add(head.val); 
    } 
} 

方法消耗情況

執(zhí)行用時：1 ms 
內(nèi)存消耗：40.5 MB 

時間復(fù)雜度

該算法相當(dāng)于遍歷了兩遍鏈表，遞推一遍，歸檔一遍，所以一共為2n。

去除常量，時間復(fù)雜度就是O(n)

空間復(fù)雜度

由于用到ArrayList和數(shù)組，所以空間復(fù)雜度也是O(n)。

解法二

第二種解法就是利用棧的特點：先入后出。(棧的知識點后面再細(xì)說)

先入后出不就是題目的需求么，從尾部倒著輸出數(shù)字。

所以我們把鏈表依次入棧，然后在依次出棧就可以完成需求了。

class Solution { 
    public int[] reversePrint(ListNode head) { 
        LinkedList<Integer> stack = new LinkedList<Integer>(); 
        while(head != null) { 
            stack.addLast(head.val); 
            head = head.next; 
        } 
        int[] res = new int[stack.size()]; 
        for(int i = 0; i < res.length; i++) 
            res[i] = stack.removeLast(); 
    return res; 
    } 
} 

方法消耗情況

執(zhí)行用時：1 ms 
內(nèi)存消耗：39.2 MB 

時間復(fù)雜度

同上一個算法一樣，時間復(fù)雜度就是入棧和出棧的時間，也就是O(n)。

空間復(fù)雜度

由于用到了stack和數(shù)組res，所以空間復(fù)雜度也是O(n)。

參考

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

https://time.geekbang.org/column/article/41013

本文轉(zhuǎn)載自微信公眾號「碼上積木」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系碼上積木公眾號。