Java 算法篇-深入了解單鏈表的反轉(zhuǎn)（實(shí)現(xiàn)：用 5 種方式來具體實(shí)現(xiàn)）

這篇具有很好參考價(jià)值的文章主要介紹了Java 算法篇-深入了解單鏈表的反轉(zhuǎn)（實(shí)現(xiàn)：用 5 種方式來具體實(shí)現(xiàn)）。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

??博客主頁(yè)：?小扳_-CSDN博客
?感謝大家點(diǎn)贊??收藏?評(píng)論???

Java 算法篇-深入了解單鏈表的反轉(zhuǎn)（實(shí)現(xiàn)：用 5 種方式來具體實(shí)現(xiàn)）,Java 數(shù)據(jù)結(jié)構(gòu)與算法篇,算法,java ?

?文章來源地址http://www.zghlxwxcb.cn/news/detail-752592.html

Java 算法篇-深入了解單鏈表的反轉(zhuǎn)（實(shí)現(xiàn)：用 5 種方式來具體實(shí)現(xiàn)）,Java 數(shù)據(jù)結(jié)構(gòu)與算法篇,算法,java

文章目錄

? ? ? ? 1.0 單鏈表的反轉(zhuǎn)說明

? ? ? ? 2.0 單鏈表的創(chuàng)建

? ? ? ? 3.0 實(shí)現(xiàn)單鏈表反轉(zhuǎn)的五種方法

? ? ? ? 3.1?實(shí)現(xiàn)單鏈表反轉(zhuǎn) - 循環(huán)復(fù)制（迭代法）

? ? ? ? 3.2 實(shí)現(xiàn)單鏈表反轉(zhuǎn) -?頭插法

? ? ? ? 3.3?實(shí)現(xiàn)單鏈表反轉(zhuǎn) -?遞歸法

? ? ? ? 3.4?實(shí)現(xiàn)單鏈表反轉(zhuǎn) -?三指針法

? ? ? ? 3.5 實(shí)現(xiàn)單鏈表反轉(zhuǎn) - 第二種頭插法

? ? ? ? 4.0 實(shí)現(xiàn)單鏈表反轉(zhuǎn)的五種完整代碼

? ? ? ? 1.0 單鏈表的反轉(zhuǎn)說明

????????單鏈表的反轉(zhuǎn)是指將鏈表中的節(jié)點(diǎn)順序逆轉(zhuǎn)，即原先的鏈表尾部變成了頭部，頭部變成了尾部。比如，[1,2,3,4,5,6,7] 將這個(gè)鏈表的值反轉(zhuǎn)得到的結(jié)果為：[7,6,5,4,3,2,1]，需要注意的是，可以用值打印出來會(huì)更好觀察鏈表反轉(zhuǎn)后的結(jié)果。

? ? ? ? 2.0 單鏈表的創(chuàng)建

? ? ? ? 具體的創(chuàng)建思路：首先要把節(jié)點(diǎn)進(jìn)行封裝成單獨(dú)的類，該類中的成員包括：int value 存放值，Node next 引用下一個(gè)節(jié)點(diǎn)。由于該節(jié)點(diǎn)類為鏈表中的一個(gè)組成部分，因此，將該類設(shè)為靜態(tài)內(nèi)部類，外部類的成員為哨兵節(jié)點(diǎn)。

代碼如下：

import java.util.Iterator;

public class Linked implements Iterable<Integer>{
    private final Node hand;
    private int size;
    static class Node {
        public int value;
        public Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public Linked() {
        hand = new Node(0,null);
    }

    public void addLast (int value) {
        Node p = hand;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new Node(value, null);
        size++;
    }
    public void addFirst(int value) {
        hand.next = new Node(value,hand.next);
        size++;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = hand.next;

            @Override
            public boolean hasNext() {

                return p != null;
            }

            @Override
            public Integer next() {
                int k = p.value;
                p = p.next;
                return k;
            }
        };

    }

}
? ? ? ? 為了方便對(duì)反轉(zhuǎn)的五種方法進(jìn)行講解，實(shí)現(xiàn)了以上的頭插節(jié)點(diǎn)、尾插節(jié)點(diǎn)、用迭代器循環(huán)節(jié)點(diǎn)的值。

本篇重點(diǎn)是反轉(zhuǎn)的五種的方法，所以對(duì)以上的實(shí)現(xiàn)的 API 不太了解的話，點(diǎn)擊以下鏈接去了解一下：? ?Java 數(shù)據(jù)結(jié)構(gòu)篇-實(shí)現(xiàn)單鏈表核心API-CSDN博客

????????3.0 實(shí)現(xiàn)單鏈表反轉(zhuǎn)的五種方法

????????迭代法：遍歷鏈表，依次改變節(jié)點(diǎn)的指針方向，使其指向前一個(gè)節(jié)點(diǎn)。

????????遞歸法：利用遞歸函數(shù)，先反轉(zhuǎn)后續(xù)節(jié)點(diǎn)，然后再將當(dāng)前節(jié)點(diǎn)的指針指向前一個(gè)節(jié)點(diǎn)。

????????頭插法：從頭到尾遍歷原鏈表，依次將每個(gè)節(jié)點(diǎn)插入到新鏈表的頭部，形成新的反轉(zhuǎn)鏈表。

????????棧：利用棧的特性，將鏈表節(jié)點(diǎn)依次入棧，然后依次出棧構(gòu)建新的反轉(zhuǎn)鏈表。

????????三指針法：使用三個(gè)指針分別指向當(dāng)前節(jié)點(diǎn)、前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)，依次改變節(jié)點(diǎn)的指針方向，實(shí)現(xiàn)鏈表的反轉(zhuǎn)。

? ? ? ? 3.1?實(shí)現(xiàn)單鏈表反轉(zhuǎn) - 循環(huán)復(fù)制（迭代法）

? ? ? ? 思路為：遍歷舊的鏈表來取得每個(gè)節(jié)點(diǎn)的對(duì)應(yīng)的值，然后新鏈表根據(jù)得到的值來創(chuàng)建節(jié)點(diǎn)進(jìn)行頭插節(jié)點(diǎn)，這樣就實(shí)現(xiàn)了鏈表反轉(zhuǎn)了。需要注意的是，這個(gè)方法并沒有改變舊鏈表。

代碼如下：

    //方法一: 循環(huán)復(fù)制
    public Linked reverseMethod1 (Linked linked) {
        Linked linked1 = new Linked();
        for (Integer integer : linked) {
            linked1.addFirst(integer);
        }
        return linked1;
    }
? ? ? ? 分析以上代碼：先創(chuàng)建一個(gè)新鏈表 linked1 然后調(diào)用頭插節(jié)點(diǎn)的方法，通過傳入舊節(jié)點(diǎn)的值來創(chuàng)建對(duì)象，也就是節(jié)點(diǎn)。需要注意的是，這里的增強(qiáng) for 循環(huán)是已經(jīng)實(shí)現(xiàn)了。

? ? ? ? 3.2 實(shí)現(xiàn)單鏈表反轉(zhuǎn) -?頭插法

? ? ? ? 通過改變舊節(jié)點(diǎn)的節(jié)點(diǎn)指向來實(shí)現(xiàn)鏈表反轉(zhuǎn)，當(dāng)反轉(zhuǎn)結(jié)束之后，舊的鏈表順序就會(huì)被改變。具體思路：先要對(duì)舊節(jié)點(diǎn)的 hand.next 頭節(jié)點(diǎn)從該鏈表獨(dú)立出來，對(duì)于舊鏈表來說就是刪除頭節(jié)點(diǎn)，不過要記錄要?jiǎng)h除的節(jié)點(diǎn)，得到這個(gè)頭節(jié)點(diǎn)之后，該節(jié)點(diǎn)頭插到新的鏈表中，一直循環(huán)往復(fù)下去，直到 hand.next == null 結(jié)束循環(huán)。

? ? ? ? 對(duì)于這個(gè)鏈表來說，這就可以把 remove 這個(gè)節(jié)點(diǎn)刪除了，也為頭刪節(jié)點(diǎn)。當(dāng) hand.next = null 就說明了沒有節(jié)點(diǎn)了，就應(yīng)該結(jié)束循環(huán)了。

? ? ? ? 這就是頭插節(jié)點(diǎn)的流程。

代碼如下：

    //方法二: 改變舊節(jié)點(diǎn)的指向
    public Linked reverseMethod2(Linked linked) {

        Linked linkedNew = new Linked();
        Node handNew = linkedNew.hand;
        while (hand.next != null) {

            //先頭刪
            Node temp = linked.hand.next;
            linked.hand.next = temp.next;
            //再頭插
            Node tp = handNew.next;
            handNew.next = temp;
            temp.next = tp;
        }
        return linkedNew;
    }
對(duì)以上代碼進(jìn)行分析：

? ? ? ? ?先創(chuàng)建一個(gè)新的鏈表，在刪除頭節(jié)點(diǎn)前，需要將要?jiǎng)h除的節(jié)點(diǎn)記錄起來，如果一個(gè)對(duì)象沒被引用就會(huì)被 JVM 自動(dòng)回收，然后頭節(jié)點(diǎn)指向刪除節(jié)點(diǎn)的指向下一個(gè)的節(jié)點(diǎn)。頭插節(jié)點(diǎn)前，需要將 hand.next 同樣要記錄，然后頭節(jié)點(diǎn)指向新的節(jié)點(diǎn)，新的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，正就是原先的 hand.next 。

? ? ? ? 3.3?實(shí)現(xiàn)單鏈表反轉(zhuǎn) -?遞歸法

? ? ? ? ?思路：通過遞歸這種方式，先遞出到 “底” ，得到舊鏈表的最后一個(gè)節(jié)點(diǎn)，所以遞歸結(jié)束的條件也就是 temp.next == null，返回該節(jié)點(diǎn) temp 也就是最后的節(jié)點(diǎn)。遞歸的函數(shù)也很容易可以想出來為：?調(diào)用自己的方法名(node.next) 。

代碼如下：

    //方法三: 遞歸
    public Linked reverseMethod3(Linked linked) {
        Linked linked1 = new Linked();
        linked1.hand.next = reversion(linked.hand.next);
        return linked1;
    }

    public Node reversion (Node node) {
        if (node == null || node.next == null) {
            return node;
        }
        Node last = reversion(node.next);
        node.next.next = node;
        node.next = null;
        return last;
    }
? ? ? ? 對(duì)以上代碼進(jìn)行分析：先創(chuàng)建一個(gè)新的鏈表 linkded1 ，調(diào)用 reversion()??這個(gè)方法來得到頭節(jié)點(diǎn)。具體來看是如何得到頭節(jié)點(diǎn)，顯而易見，就是通過遞歸，遞到底（到盡頭）取到最后一個(gè)節(jié)點(diǎn)，然后將這個(gè)尾節(jié)點(diǎn)一直返回出來，OK，這里就拿到了新鏈表的頭節(jié)點(diǎn)了。接下來要考慮的是，如何將剩下的節(jié)點(diǎn)反轉(zhuǎn)呢？

?先來看看遞歸的流程圖：

? ? ?

分析如下：??

????????假設(shè)有五個(gè)節(jié)點(diǎn)，在遞歸回歸的過程中，需要做的事第五個(gè)節(jié)點(diǎn)指向第四個(gè)節(jié)點(diǎn)，第四個(gè)節(jié)點(diǎn)指向第三個(gè)節(jié)點(diǎn)...一直下去，這樣是不是就實(shí)現(xiàn)了每個(gè)節(jié)點(diǎn)指向都反轉(zhuǎn)了。但是需要注意的是，當(dāng)?shù)诙€(gè)節(jié)點(diǎn)指向第一個(gè)節(jié)點(diǎn)，這里都沒有問題，我們很容易會(huì)忽略，第一個(gè)節(jié)點(diǎn)原先就指向第二個(gè)節(jié)點(diǎn)，因此，會(huì)出現(xiàn)死循環(huán)，解決辦法：先暫時(shí)將被指向的節(jié)點(diǎn)賦值為：null ，這樣就完美解決了。

? ? ? ? 3.4?實(shí)現(xiàn)單鏈表反轉(zhuǎn) -?三指針法

? ? ? ? 實(shí)現(xiàn)思路：在原先鏈表中進(jìn)行改變每個(gè)節(jié)點(diǎn)的引用，先定義出三個(gè)變量分別為 o1，o2，n1，一開始的時(shí)候 o1 , n1指向鏈表中的 hand?頭節(jié)點(diǎn)（先來搞定沒有哨兵的鏈表），對(duì)于 o2 指向 hand.next 。接下來就可以開始移動(dòng) o2，n1 這個(gè)兩個(gè)指針了，主要的是 o1 保持不變，永遠(yuǎn)指向 hand 節(jié)點(diǎn)，先讓 hand.next = o2.next ，這個(gè)意思就是將 hand.next 的頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)從鏈表中移出，然后將移出來的節(jié)點(diǎn)指向 n1 ，最后 o2 = n1 將 n1 賦值給 o2 ，o2 再接著指向 hand.next 的節(jié)點(diǎn)。

幾個(gè)簡(jiǎn)單的過程：

代碼如下：

    //方法四:雙引用
    public Linked reverseMethod4(Linked linked) {
        linked.hand.next = dualPointers(linked.hand.next);
        return linked;
    }

    public Node dualPointers(Node hand) {
        Node o1 = hand;
        Node n1 = hand;
        Node o2 = o1.next;
        while (o2 != null) {
            o1.next = o2.next;
            o2.next = n1;
            n1 = o2;
            o2 = o1.next;
        }
        return n1;
    }
????????通過以上的簡(jiǎn)單幾個(gè)過程且結(jié)合代碼來分析，應(yīng)該會(huì)有一點(diǎn)點(diǎn)感覺，來總結(jié)以下，對(duì)于 o1 的動(dòng)作就是站在 hand 節(jié)點(diǎn)中 "一動(dòng)不動(dòng)"，對(duì)于 o2 可以將它看作搬運(yùn)工，不斷搬運(yùn) hand.next 的節(jié)點(diǎn)運(yùn)到 n1 節(jié)點(diǎn)的前面（n1 的左邊），具體就是先要將 o2.next 節(jié)點(diǎn)被 hand.next 引用，接著就是搬運(yùn)了， o2.next 指向 n1 的節(jié)點(diǎn)，然后 n1 需要往后跳一格（往左邊移動(dòng)一個(gè)節(jié)點(diǎn)）即將 o2 賦值給 n1，然后 o2 就返回去指向 o1.next 的節(jié)點(diǎn)了，循環(huán)往復(fù)下去，直到當(dāng) o1.next == null 時(shí)，就該結(jié)束循環(huán)了。

? ? ? ? 3.5 實(shí)現(xiàn)單鏈表反轉(zhuǎn) - 第二種頭插法

? ? ? ? 思路：遍歷舊鏈表的每一個(gè)節(jié)點(diǎn)，然后直接插入到新鏈表中，這個(gè)方法個(gè)第一種頭插很相似，區(qū)別就是第一種頭插的方法是面向?qū)ο缶幊痰?，第二種頭插的方法是面向過程來編程的。

代碼如下：

    //方法五:
    public Linked reverseMethod5(Linked linked) {
        Node o1 = linked.hand.next;
        Linked linked1 = new Linked();
        Node n1 = null;
        while (o1 != null) {
            Node temp = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = temp;
        }
       linked1.hand.next = n1;
        return linked1;
    }
? ? ? ? 這里也運(yùn)用到了頭刪還有頭插，跟之前的頭插有所不同，這里的頭插是將插入進(jìn)來的節(jié)點(diǎn)變成為新鏈表的頭節(jié)點(diǎn)，直到遍歷結(jié)束為止。

? ? ? ? 4.0 實(shí)現(xiàn)單鏈表反轉(zhuǎn)的五種完整代碼

import java.util.Iterator;

public class Linked implements Iterable<Integer>{
    public Node hand;
    private int size;
    static class Node {
        public int value;
        public Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public Linked() {
        hand = new Node(0,null);
    }

    public void addLast (int value) {
        Node p = hand;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new Node(value, null);
        size++;
    }
    public void addFirst(int value) {
        hand.next = new Node(value,hand.next);
        size++;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = hand.next;

            @Override
            public boolean hasNext() {

                return p != null;
            }

            @Override
            public Integer next() {
                int k = p.value;
                p = p.next;
                return k;
            }
        };

    }



    //方法一: 循環(huán)復(fù)制
    public Linked reverseMethod1 (Linked linked) {
        Linked linked1 = new Linked();
        for (Integer integer : linked) {
            linked1.addFirst(integer);
        }
        return linked1;
    }

    //方法二: 改變舊節(jié)點(diǎn)的指向
    public Linked reverseMethod2(Linked linked) {

        Linked linkedNew = new Linked();
        Node handNew = linkedNew.hand;
        while (hand.next != null) {

            //先頭刪
            Node temp = linked.hand.next;
            linked.hand.next = temp.next;
            //再頭插
            Node tp = handNew.next;
            handNew.next = temp;
            temp.next = tp;
        }
        return linkedNew;
    }

    //方法三: 遞歸
    public Linked reverseMethod3(Linked linked) {
        Linked linked1 = new Linked();
        linked1.hand.next = reversion(linked.hand.next);
        return linked1;
    }

    public Node reversion (Node node) {
        if (node == null || node.next == null) {
            return node;
        }
        Node last = reversion(node.next);
        node.next.next = node;
        node.next = null;
        return last;
    }

    //方法四:雙引用
    public Linked reverseMethod4(Linked linked) {
        linked.hand.next = dualPointers(linked.hand.next);
        return linked;
    }

    public Node dualPointers(Node hand) {
        Node o1 = hand;
        Node n1 = hand;
        Node o2 = o1.next;
        while (o2 != null) {
            o1.next = o2.next;
            o2.next = n1;
            n1 = o2;
            o2 = o1.next;
        }
        return n1;
    }

    //方法五:
    public Linked reverseMethod5(Linked linked) {
        Node o1 = linked.hand.next;
        Linked linked1 = new Linked();
        Node n1 = null;
        while (o1 != null) {
            Node temp = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = temp;
        }
       linked1.hand.next = n1;
        return linked1;
    }

}

Java 算法篇-深入了解單鏈表的反轉(zhuǎn)（實(shí)現(xiàn)：用 5 種方式來具體實(shí)現(xiàn)）,Java 數(shù)據(jù)結(jié)構(gòu)與算法篇,算法,java

到了這里，關(guān)于Java 算法篇-深入了解單鏈表的反轉(zhuǎn)（實(shí)現(xiàn)：用 5 種方式來具體實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！