【劍指Offer第三題】從尾到頭打印鏈表-創(chuàng)新互聯(lián)

題目描述
輸入一個(gè)鏈表，按鏈表從尾到頭的順序返回一個(gè)ArrayList。
網(wǎng)站的建設(shè)創(chuàng)新互聯(lián)建站專注網(wǎng)站定制,經(jīng)驗(yàn)豐富,不做模板,主營網(wǎng)站定制開發(fā).小程序定制開發(fā),H5頁面制作!給你煥然一新的設(shè)計(jì)體驗(yàn)!已為成都銅雕雕塑等企業(yè)提供專業(yè)服務(wù)。

注：設(shè)鏈表長度為n。語言：C++

鏈表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)規(guī)定如下：

*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };

解法1：正向遍歷，借助反向迭代器實(shí)現(xiàn)序列逆置（C++特性）。

vector<int> printListFromTailToHead(ListNode* head) {
        ListNode *p;
        p = head;
        vector<int> array;
        while(p != NULL)
        {
            array.push_back(p->val);
            p = p->next;
        }
        return vector<int>(array.rbegin(), array.rend());
    }

時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(1)

解法2：借助棧先進(jìn)后出的特性，將鏈表結(jié)點(diǎn)先入棧后出棧，再壓入序列中。

vector<int> printListFromTailToHead(ListNode* head) {
        ListNode *p;
        p = head;
        stack<int> s;
        while(p != NULL)
        {
            s.push(p->val);
            p = p->next;
        }
        p = head;
        vector<int> array;
        while(p != NULL)
        {
            array.push_back(s.top());
            s.pop();
            p = p->next;
        }
        return array;
    }

時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(n)

解法3：遞歸

    vector<int> array;
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode *p;
        p = head;
        if(head != NULL)
        {
            if(head->next != NULL)
                printListFromTailToHead(head->next);
            array.push_back(head->val);
        }
        return array;
    }

時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(n)

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

文章題目：【劍指Offer第三題】從尾到頭打印鏈表-創(chuàng)新互聯(lián)
新聞來源：http://muchs.cn/article24/eiece.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、網(wǎng)站設(shè)計(jì)、網(wǎng)站導(dǎo)航、用戶體驗(yàn)、網(wǎng)站建設(shè)、做網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容