劍指Offer_編程題_從尾到頭打印鏈表

行者花雕 2020-05-25

展開全文

題目描述

輸入一個鏈表，按鏈表從尾到頭的順序返回一個ArrayList。

答案

有三種思路，

第一就是利用棧先入后出的特性完成，

第二就是存下來然后進行數(shù)組翻轉(zhuǎn)。

第三是利用遞歸。

// 數(shù)組反轉(zhuǎn)實現(xiàn)方式

作者：小輝哥哥
鏈接：https://www./questionTerminal/d0267f7f55b3412ba93bd35cfa8e8035?f=discussion
來源：?？途W(wǎng)

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        ListNode pre=null;
        ListNode next=null;
        while(listNode!=null){
            next=listNode.next;
            listNode.next=pre;
            pre=listNode;
            listNode=next;
        }
        while(pre!=null){
            list.add(pre.val);
            pre=pre.next;
        }
        return list;
    }
}

鏈接：https://www./questionTerminal/d0267f7f55b3412ba93bd35cfa8e8035?f=discussion
來源：?？途W(wǎng)

java 遞歸超簡潔版本

public class Solution {

ArrayList<Integer> arrayList=new ArrayList<Integer>();

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

if(listNode!=null){

this.printListFromTailToHead(listNode.next);

arrayList.add(listNode.val);

}

return arrayList;

}

創(chuàng)建鏈表相關(guān)，頭插法和尾插法

關(guān)于頭插法，可以next可以理解成前一個節(jié)點地址，插入順序：

1、頭節(jié)點傳入，開始創(chuàng)建A數(shù)據(jù)，頭節(jié)點的next指向A數(shù)據(jù)的內(nèi)存地址，A節(jié)點的next替換成頭節(jié)點的

2、頭節(jié)點再傳入，創(chuàng)建B數(shù)據(jù)，頭節(jié)點的next又換成了指向B的內(nèi)存地址，B節(jié)點的next替換頭節(jié)點的A；

總結(jié)一下：插入時候，一直在頭節(jié)點的上面插入數(shù)據(jù)，原來的數(shù)據(jù)被“頂”上去了；

　　　　　頭插法遍歷的時候，頭節(jié)點開始，一個一個往上遍歷。這樣最后插入的就作為第一個輸出出來了；

　　　　　尾插法編練插入，比較好理解，就是一直在“尾巴”追加，遍歷時候從頭開始，第一個插入的就第一個輸出出來；　

public class Test {

    static Node headNode;

    class Node {
        private Node next;//指針
        private int data;//數(shù)據(jù)域
    }

    //尾插法創(chuàng)建單鏈表  隊列形式先進先出
    public void back(Node node, int data) {
        if (data < 10) {
            Node next = new Node();
            next.data = data;
            next.next = null;
            node.next = next;
            back(next, ++data);
        }
    }

    //頭插法創(chuàng)建單鏈表  棧形式先進后出
    public void head(Node node, int data) {

        if (data < 10) {
            Node next = new Node();
            next.next = node.next;


            next.data = data;
            node.next = next;
            System.out.println("遞歸參數(shù)：" + node.data);
            head(node, ++data);
        }
    }

    public static void main(String[] args) {
        Test test = new Test();
        headNode = test.new Node();//頭指針
//        new Test().back(headNode, 0);//前插法
        new Test().head(headNode, 0);//后插法
        System.out.println("創(chuàng)建后的鏈表是：");//0 1 2 3 4 5 6 7 8 9 10
        while (headNode.next != null) {
            headNode = headNode.next;
            System.out.print(headNode.data + " ");
        }
    }

}

//————————————————
//版權(quán)聲明：本文為CSDN博主「另一個絕影」的原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
//原文鏈接：https://blog.csdn.net/weixin_37817685/article/details/83305972