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

?

?

文章目錄

? ? ? ? 1.0 鏈表的創(chuàng)建

????????2.0 判斷回文鏈表說明

? ? ? ? 2.1 快慢指針方法

????????2.2 使用遞歸方式實(shí)現(xiàn)反轉(zhuǎn)鏈表方法

? ? ? ? 2.3 實(shí)現(xiàn)判斷回文鏈表 - 使用快慢指針與反轉(zhuǎn)鏈表方法

? ? ? ? 3.0 判斷環(huán)鏈表說明

? ? ? ? 3.1 實(shí)現(xiàn)判斷環(huán)鏈表與尋找環(huán)入口節(jié)點(diǎn)?- "龜兔賽跑"算法實(shí)現(xiàn)

????????3.2 解釋為什么第一次相遇后，兔、龜每一次都走一步最終會(huì)相遇且該節(jié)點(diǎn)是環(huán)入口節(jié)點(diǎn)的原因

? ? ? ? 4.0 實(shí)現(xiàn)判斷回文鏈表、判斷環(huán)鏈表且尋找環(huán)入口節(jié)點(diǎn)的完整代碼

?

? ? ? ? 1.0 鏈表的創(chuàng)建

????????鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)一系列元素。鏈表由節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素和一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針。鏈表可以分為單向鏈表和雙向鏈表，其中單向鏈表的節(jié)點(diǎn)只有一個(gè)指針指向下一個(gè)節(jié)點(diǎn)，而雙向鏈表的節(jié)點(diǎn)有兩個(gè)指針，分別指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)。? ? ? ??

????????為后續(xù)實(shí)現(xiàn)算法方便，這里需要實(shí)現(xiàn)一個(gè)帶哨兵節(jié)點(diǎn)的單鏈表。

代碼如下：

import java.util.Iterator;

public class List implements Iterable<Integer>{
    private final Node sentry;

    static class Node {
        public int value;
        public Node next;

        public Node() {
        }

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

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value + "}";
        }
    }

    //外部類構(gòu)造器，初始化哨兵節(jié)點(diǎn)
    public List() {
        sentry = new Node(-1,null);
    }

    //頭插節(jié)點(diǎn)
    public void addFirst(int value) {
        this.sentry.next = new Node(value,this.sentry.next);
    }

    //尾插節(jié)點(diǎn)
    public void addLats(int value) {
        Node p = this.sentry;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new Node(value,null);
    }

    //重寫迭代器
    @Override
    public Iterator<Integer> iterator() {

        return new Iterator<Integer>() {
            Node p = sentry.next;

            @Override
            public boolean hasNext() {
                return p != null;
            }

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

}

? ? ? ? 簡(jiǎn)單對(duì)以上代碼進(jìn)行分析：將鏈表進(jìn)行封裝成一個(gè)外部類，靜態(tài)內(nèi)部類則是節(jié)點(diǎn)類進(jìn)行封裝。外部類的成員變量為一個(gè)哨兵節(jié)點(diǎn)，內(nèi)部類的成員變量為 int value 值、 Node next 指向下一個(gè)節(jié)點(diǎn)的引用變量。外部類實(shí)現(xiàn)了頭插節(jié)點(diǎn)、尾插節(jié)點(diǎn)、重寫了迭代器等。

需要了解可以點(diǎn)擊該鏈接：Java 數(shù)據(jù)結(jié)構(gòu)篇-實(shí)現(xiàn)單鏈表核心API-CSDN博客

?

????????2.0 判斷回文鏈表說明

????????回文鏈表是指一個(gè)鏈表從頭到尾和從尾到頭讀是一樣的，也就是說，鏈表的節(jié)點(diǎn)值按照順序排列和逆序排列是相同的。例如，鏈表 1 -> 2 -> 3 -> 2 -> 1 就是一個(gè)回文鏈表，因?yàn)閺念^到尾讀和從尾到頭讀都是 1 -> 2 -> 3 -> 2 -> 1。

? ? ? ? 2.1 快慢指針方法

? ? ? ? 實(shí)現(xiàn)判斷回文鏈表時(shí)需要用到快慢指針方法來尋找中間節(jié)點(diǎn)。

? ? ? ? 具體思路：實(shí)現(xiàn)快慢指針找中間節(jié)點(diǎn)，定義兩個(gè)指針，對(duì)于 fast 指針來說，每一次循環(huán)都要走兩步，直到 fast == null 或者 fast.next == null，遇到這兩種情況都要結(jié)束循環(huán)了，注意不要缺少了 fast.next == null 的情況，不然有可能拋出 "空指針異常" ；對(duì)于 slow 指針來說，每一次循環(huán)都要走一步，直到退出循環(huán)后，若鏈表的節(jié)點(diǎn)的數(shù)量為奇數(shù)時(shí)，則指向的節(jié)點(diǎn)就是中間節(jié)點(diǎn)。

????????若鏈表的節(jié)點(diǎn)的數(shù)量為偶數(shù)時(shí)，則指向的節(jié)點(diǎn)是中間兩個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)。例如鏈表?1 -> 2 -> 3 -> 3 ->?2 -> 1 -> null，此時(shí)循環(huán)結(jié)束后，slow 指針指向的是靠后面值為 3 的節(jié)點(diǎn)。

代碼如下：

    //查找鏈表中的中間的節(jié)點(diǎn)(快慢指針):假如為奇數(shù)，則需要找到中間的節(jié)點(diǎn)；
    // 假如是偶數(shù)，則需要找到中間的兩個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)。
    public Node searchMidNode() {
        //判斷是否為空鏈表
        if (this.sentry.next == null) {
            return null;
        }

        Node fast = this.sentry.next;
        Node slow = this.sentry.next;
        while (fast!= null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

????????2.2 使用遞歸方式實(shí)現(xiàn)反轉(zhuǎn)鏈表方法

? ? ? ? 實(shí)現(xiàn)判斷回文鏈表時(shí)需要實(shí)現(xiàn)反轉(zhuǎn)鏈表。

? ? ? ? 具體思路：先考慮遞出的終止條件為：當(dāng) p.next == null 時(shí)，則返回 p 這個(gè)節(jié)點(diǎn)。再考慮在回歸的過程中，需要將該 p 節(jié)點(diǎn)一直回歸到回歸過程結(jié)束為止。還需要將每一個(gè)節(jié)點(diǎn)都需要反轉(zhuǎn)一下，p.next.next = p，注意這里需要將 p.next?"暫時(shí)" 置為 null ，p.next = null，否則會(huì)陷入死循環(huán)中。

代碼如下：

    //用遞歸實(shí)現(xiàn)鏈表反轉(zhuǎn)
    public Node reverseRecursion(Node p) {
        if (p.next == null) {
            return p;
        }

        Node last = reverseRecursion(p.next);
        p.next.next = p;
        p.next = null;
        return last;
    }

?????????用遞歸實(shí)現(xiàn)鏈表反轉(zhuǎn)是其中一種的方法，還有四種方法可以實(shí)現(xiàn)鏈表反轉(zhuǎn)，需要了解可以點(diǎn)擊一下鏈接：Java 算法篇-深入了解單鏈表的反轉(zhuǎn)（實(shí)現(xiàn)：用 5 種方式來具體實(shí)現(xiàn)）-CSDN博客?

? ? ? ? 2.3 實(shí)現(xiàn)判斷回文鏈表 - 使用快慢指針與反轉(zhuǎn)鏈表方法

????????具體思路為：先找到鏈表中的中間節(jié)點(diǎn)，例如鏈表 1 -> 2 -> 3 -> 2 -> 1 -> null ，需要先找節(jié)點(diǎn)值為：3 的節(jié)點(diǎn)，可以用快慢指針來實(shí)現(xiàn)找中間節(jié)點(diǎn)。然后將該節(jié)點(diǎn)后面的鏈表( 3 -> 2 -> 1 -> null )進(jìn)行反轉(zhuǎn)，可以用遞歸來實(shí)現(xiàn)反轉(zhuǎn)的鏈表，得 1 -> 2 -> 3 -> null 。接著，用舊鏈表進(jìn)行與反轉(zhuǎn)后的鏈表遍歷比較，若出現(xiàn)不相同值的節(jié)點(diǎn)，則判斷該鏈表不是回文鏈表；若遍歷完都沒有返回 false ，則判斷該鏈表為回文鏈表。

代碼如下：

    //查找鏈表中的中間的節(jié)點(diǎn)(快慢指針):假如為奇數(shù)，則需要找到中間的節(jié)點(diǎn)；
    // 假如是偶數(shù)，則需要找到中間的兩個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)。
    public Node searchMidNode() {
        //判斷是否為空鏈表
        if (this.sentry.next == null) {
            return null;
        }

        Node fast = this.sentry.next;
        Node slow = this.sentry.next;
        while (fast!= null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    //用遞歸實(shí)現(xiàn)鏈表反轉(zhuǎn)
    public Node reverseRecursion(Node p) {
        if (p.next == null) {
            return p;
        }

        Node last = reverseRecursion(p.next);
        p.next.next = p;
        p.next = null;
        return last;
    }



    //判斷是否為回文鏈表
    public boolean isPalindromeList() {
        Node p = this.sentry.next;

        //需要先找到中間節(jié)點(diǎn)
        Node midNode = this.searchMidNode();
        //然后將中間節(jié)點(diǎn)往后的鏈表進(jìn)行反轉(zhuǎn)，反轉(zhuǎn)可以用遞歸的方法。
        Node newMidNode = reverseRecursion(midNode);
        //接下來就要對(duì)舊節(jié)點(diǎn)的前半段鏈表進(jìn)行循環(huán)遍歷來比較了每一個(gè)節(jié)點(diǎn)的值是否相同了
        //當(dāng)且僅當(dāng)，當(dāng)?shù)椒崔D(zhuǎn)后的鏈表的最后一個(gè)為 null 時(shí)，結(jié)束循環(huán)
        while (newMidNode != null) {
            if (p.value != newMidNode.value) {
                return false;
            }
            p = p.next;
            newMidNode = newMidNode.next;
        }
        return true;

    }

? ? ? ? 需要注意的是，對(duì)與 p 鏈表來說，一旦實(shí)現(xiàn)了鏈表反轉(zhuǎn)， p 自身的鏈表會(huì)改變。反轉(zhuǎn)之后的鏈表 newMidNode == null 時(shí)，就該結(jié)束循環(huán)了。而不能以 p == null 作為結(jié)束循環(huán)條件，原因是當(dāng)鏈表的節(jié)點(diǎn)為偶數(shù)時(shí)，那么反轉(zhuǎn)后的鏈表會(huì)比 p 鏈表少一個(gè)節(jié)點(diǎn)，假如用 p == null 作為結(jié)束循環(huán)的條件，那么當(dāng)鏈表的節(jié)點(diǎn)數(shù)為偶數(shù)時(shí)，肯定會(huì)報(bào) "空指針異常"，所以需要以 newMidNode == null 作為循環(huán)結(jié)束條件。

? ? ? ? 3.0 判斷環(huán)鏈表說明

????????環(huán)鏈表是指鏈表中至少有一個(gè)節(jié)點(diǎn)的 next 指針指向了鏈表中的一個(gè)已經(jīng)存在的節(jié)點(diǎn)，使得鏈表中存在環(huán)形結(jié)構(gòu)。換句話說，鏈表中的一個(gè)節(jié)點(diǎn)的 next 指針指向了之前的某個(gè)節(jié)點(diǎn)，導(dǎo)致鏈表中存在環(huán)。

? ? ? ? 3.1 實(shí)現(xiàn)判斷環(huán)鏈表與尋找環(huán)入口節(jié)點(diǎn)?- "龜兔賽跑"算法實(shí)現(xiàn)

? ? ? ? 具體思路：先來判斷是否為環(huán)鏈表，可以比作為龜與兔的實(shí)際情景，當(dāng)龜每一次走一步時(shí)，兔每一次走兩步。即在相同時(shí)間下，兔所走的路程時(shí)龜?shù)膬杀?/span>。

????????情況一：當(dāng)兔第一次沒有追上龜時(shí)，則不是環(huán)鏈表，直接返回 null 。

????????情況二：當(dāng)兔第一次追上了龜時(shí)，可以判斷為該鏈表為環(huán)形鏈表。接著尋找環(huán)入口，步驟為：可以借助兔子來記錄第一次相遇的節(jié)點(diǎn)，對(duì)于龜來說，移到頭節(jié)點(diǎn)開始一步步走，同時(shí)，兔子這次也是一步步走，當(dāng)他們第二次相遇時(shí)，當(dāng)前節(jié)點(diǎn)就為環(huán)入口節(jié)點(diǎn)。

代碼如下：

    //判斷是否閉環(huán)，如果是返回，則返回?fù)Q入口；如果不是，則返回 null
    public Node isLoop() {
        Node fast = this.sentry.next;
        Node slow = this.sentry.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;


            if (slow == fast) {
                slow = this.sentry.next;

                //特例：當(dāng)鏈表成為一個(gè)大環(huán)的時(shí)候(頭尾相連),則直接返回

                //再相遇即為換入口節(jié)點(diǎn)
                while (true) {
                    if (slow == fast) {
                        return slow;
                    }
                    slow = slow.next;
                    fast = fast.next;

                }
            }
        }
        //從循環(huán)出來的不是閉環(huán)
        return null;
    }

????????需要注意的是，當(dāng)該鏈表是首尾相連時(shí)，第一次相遇時(shí)，不用再走第二次了，因?yàn)榇藭r(shí)正好是環(huán)入口節(jié)點(diǎn)，直接返回當(dāng)前節(jié)點(diǎn)。因此第一次相遇之后，將龜移到頭節(jié)點(diǎn)處，接著就要判斷此時(shí)龜與兔此時(shí)是否為同一個(gè)節(jié)點(diǎn)。否則，將龜移到頭節(jié)點(diǎn)處后，沒有先判斷龜與兔是否為同一個(gè)節(jié)點(diǎn)，而將龜、兔同時(shí)走向下一步時(shí)，就會(huì)進(jìn)入判斷 if(slow == fast)，返回已經(jīng)相對(duì)與環(huán)節(jié)點(diǎn)的下一個(gè)的節(jié)點(diǎn)。

????????3.2 解釋為什么第一次相遇后，兔、龜每一次都走一步最終會(huì)相遇且該節(jié)點(diǎn)是環(huán)入口節(jié)點(diǎn)的原因

? ? ? ? 假設(shè)，起點(diǎn)到環(huán)入口點(diǎn)的距離為 a 個(gè)節(jié)點(diǎn)，n 為在環(huán)中轉(zhuǎn)的圈數(shù)，k 為在圈中走的節(jié)點(diǎn)數(shù)(可以理解為不夠一圈的余數(shù))。可以得出一條公式：h = a + n 無論 n 為多少，h 都會(huì)剛好來到環(huán)入口處。

????????那么在龜、兔第一次相遇時(shí)，對(duì)于龜來說，走了 g = a + n1 + k，對(duì)于兔來說，走了 t = a + n2 + k，對(duì)于 n1 ，n2 來說是多少都不在乎，但是兩者的 k 、a 是一樣的。上面說到，在第一次相遇的時(shí)候，兔所走的距離恰好是龜?shù)木嚯x的兩倍，則龜走的距離 = 兔走的距離 - 龜走的距離，由此可得，相當(dāng)與將龜走的距離換算為圈數(shù)： g = t - g = n2 - n1 ，g = n3，n3 具體是多少圈不在乎，反正知道是走了圈數(shù)，那么結(jié)合 a + n 永遠(yuǎn)走到的是環(huán)入口節(jié)點(diǎn)，那么 n3 再加上 a 是不是也會(huì)走到環(huán)入口處？

? ? ? ? 所以此時(shí)，利用兔在與龜?shù)牡谝淮蜗嘤龅墓?jié)點(diǎn)，與龜重新移回頭節(jié)點(diǎn)處，接著龜與兔每一次走一步，知道他們相遇時(shí)所在的節(jié)點(diǎn)即為環(huán)入口節(jié)點(diǎn)。

?

? ? ? ? 4.0 實(shí)現(xiàn)判斷回文鏈表、判斷環(huán)鏈表且尋找環(huán)入口節(jié)點(diǎn)的完整代碼

import java.util.Iterator;

public class List implements Iterable<Integer>{
    private final Node sentry;

    static class Node {
        public int value;
        public Node next;

        public Node() {
        }

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

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value + "}";
        }
    }

    //外部類構(gòu)造器，初始化哨兵節(jié)點(diǎn)
    public List() {
        sentry = new Node(-1,null);
    }

    //頭插節(jié)點(diǎn)
    public void addFirst(int value) {
        this.sentry.next = new Node(value,this.sentry.next);
    }

    //尾插節(jié)點(diǎn)
    public void addLats(int value) {
        Node p = this.sentry;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new Node(value,null);
    }

    //重寫迭代器
    @Override
    public Iterator<Integer> iterator() {

        return new Iterator<Integer>() {
            Node p = sentry.next;

            @Override
            public boolean hasNext() {
                return p != null;
            }

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

    //查找鏈表中的中間的節(jié)點(diǎn)(快慢指針):假如為奇數(shù)，則需要找到中間的節(jié)點(diǎn)；
    // 假如是偶數(shù)，則需要找到中間的兩個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)。
    public Node searchMidNode() {
        //判斷是否為空鏈表
        if (this.sentry.next == null) {
            return null;
        }

        Node fast = this.sentry.next;
        Node slow = this.sentry.next;
        while (fast!= null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    //判斷是否為回文鏈表
    public boolean isPalindromeList() {
        Node p = this.sentry.next;

        //需要先找到中間節(jié)點(diǎn)
        Node midNode = this.searchMidNode();
        //然后將中間節(jié)點(diǎn)往后的鏈表進(jìn)行反轉(zhuǎn)，反轉(zhuǎn)可以用遞歸的方法。
        Node newMidNode = reverseRecursion(midNode);
        //接下來就要對(duì)舊節(jié)點(diǎn)的前半段鏈表進(jìn)行循環(huán)遍歷來比較了每一個(gè)節(jié)點(diǎn)的值是否相同了
        //當(dāng)且僅當(dāng)，當(dāng)?shù)椒崔D(zhuǎn)后的鏈表的最后一個(gè)為 null 時(shí)，結(jié)束循環(huán)
        while (newMidNode != null) {
            if (p.value != newMidNode.value) {
                return false;
            }
            p = p.next;
            newMidNode = newMidNode.next;
        }
        return true;

    }

    //用遞歸實(shí)現(xiàn)鏈表反轉(zhuǎn)
    public Node reverseRecursion(Node p) {
        if (p.next == null) {
            return p;
        }

        Node last = reverseRecursion(p.next);
        p.next.next = p;
        p.next = null;
        return last;
    }


    //判斷是否閉環(huán)，如果是返回，則返回?fù)Q入口；如果不是，則返回 null
    public Node isLoop() {
        Node fast = this.sentry.next;
        Node slow = this.sentry.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;


            if (slow == fast) {
                slow = this.sentry.next;

                //特例：當(dāng)鏈表成為一個(gè)大環(huán)的時(shí)候(頭尾相連),則直接返回

                //再相遇即為換入口節(jié)點(diǎn)
                while (true) {
                    if (slow == fast) {
                        return slow;
                    }
                    slow = slow.next;
                    fast = fast.next;

                }
            }
        }
        //從循環(huán)出來的不是閉環(huán)
        return null;
    }

}

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

到了這里，關(guān)于Java 算法篇-鏈表的經(jīng)典算法：判斷回文鏈表、判斷環(huán)鏈表與尋找環(huán)入口節(jié)點(diǎn)(“龜兔賽跑“算法實(shí)現(xiàn))的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！