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

?

?

文章目錄

? ? ? ? ?1.0 鏈表的說(shuō)明

? ? ? ? ?2.0 有序鏈表去重的實(shí)現(xiàn)方式

? ? ? ? 2.1 有序鏈表去重(保留重復(fù)的節(jié)點(diǎn)) -?使用遞歸來(lái)實(shí)現(xiàn)

? ? ? ? 2.2?有序鏈表去重(保留重復(fù)的節(jié)點(diǎn)) -?使用雙指針來(lái)實(shí)現(xiàn)

? ? ? ? 2.3?有序鏈表去重(不保留重復(fù)的節(jié)點(diǎn)) -?使用遞歸來(lái)實(shí)現(xiàn)

? ? ? ? 2.4?有序鏈表去重(不保留重復(fù)的節(jié)點(diǎn)) -?使用三指針來(lái)實(shí)現(xiàn)

? ? ? ? 3.0 合并升序鏈表

? ? ? ? 3.1?合并升序鏈表(兩個(gè)鏈表)?- 迭代法

? ? ? ? 3.2?合并升序鏈表(兩個(gè)鏈表)?- 遞歸法

? ? ? ? 3.3 合并多個(gè)升序鏈表

? ? ? ? 4.0 實(shí)現(xiàn)有序鏈表去重、合并升序鏈表的完整代碼

? ? ? ? 1.0 鏈表的說(shuō)明

? ? ? ? 為了更好的講解本篇當(dāng)中的兩種經(jīng)典算法，先創(chuàng)建一個(gè)帶哨兵的鏈表。鏈表是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)一系列元素。鏈表由一系列節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素和一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針。

代碼如下：

import java.util.Iterator;

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

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

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

    public List() {
        sentry = new Node(-1,null);
    }

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

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

    //重寫(xiě)迭代器
    @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 value = p.value;
                p = p.next;
                return value;
            }
        };
    }

}

? ? ? ? 簡(jiǎn)單講解一下，創(chuàng)建了一個(gè)鏈表類(lèi)，該類(lèi)中包含一個(gè)靜態(tài)內(nèi)部類(lèi)，即節(jié)點(diǎn)類(lèi)，還實(shí)現(xiàn)了一個(gè)基本的方法：頭插節(jié)點(diǎn)、尾插節(jié)點(diǎn)、重寫(xiě)了迭代器等等。

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

? ? ? ? ?2.0 有序鏈表去重的實(shí)現(xiàn)方式

? ? ? ? 在此之前，需要分為兩個(gè)方向：

????????一、需要保留重復(fù)值的節(jié)點(diǎn)

? ? ? ? 使用遞歸來(lái)實(shí)現(xiàn)有序鏈表的去重、使用雙指針來(lái)實(shí)現(xiàn)有序鏈表的去重。

????????二、不需要保留重復(fù)值的節(jié)點(diǎn)

? ? ? ? 使用遞歸來(lái)實(shí)現(xiàn)有序鏈表的去重、使用三指針來(lái)實(shí)現(xiàn)有序鏈表的去重。

? ? ? ? 2.1 有序鏈表去重(保留重復(fù)的節(jié)點(diǎn)) -?使用遞歸來(lái)實(shí)現(xiàn)

? ? ? ? 具體思路：先來(lái)考慮終止遞出的條件為：p == null 或者 p.next == null ，對(duì)于 p == null 情況，當(dāng)該鏈表為空鏈表時(shí)，直接返回 null ，對(duì)于 p.next == null 情況，當(dāng)遞出到最后只剩一個(gè)時(shí)，也沒(méi)有必要繼續(xù)下去了，不會(huì)再有重復(fù)的值的節(jié)點(diǎn)了。再來(lái)考慮遞出的具體過(guò)程：當(dāng) p.value == p.next.value 的情況，就該忽略該節(jié)點(diǎn)，則需要返回下一個(gè)節(jié)點(diǎn)；當(dāng) p.value != p.next.value 的情況，就需要返回該節(jié)點(diǎn)，但是在返回之前，需要對(duì) p.next 該節(jié)點(diǎn)的指向進(jìn)行重整。

代碼如下：

    //去重方法一(保留):遞歸
    public List removeRecursion(List list) {
        Node sentry1 = list.sentry;
        sentry = recursion1(sentry1);
        return list;
    }

    private Node recursion1(Node p) {

        if (p == null || p.next == null) {
            return p;
        }
        if (p.value == p.next.value) {
            return recursion1(p.next);
        }else {
            p.next = recursion1(p.next);
            return p;
        }

    }

? ? ? ? 需要注意的是，先得判斷鏈表對(duì)象是否為 null ，不然會(huì)空指針異常。

? ? ? ? 2.2?有序鏈表去重(保留重復(fù)的節(jié)點(diǎn)) -?使用雙指針來(lái)實(shí)現(xiàn)

? ? ? ? 具體思路：定義兩個(gè)指針 n1 與 n2 ，對(duì)于 n1 來(lái)說(shuō)：n1 一開(kāi)始指向頭節(jié)點(diǎn)，假如指向哨兵節(jié)點(diǎn)時(shí)，那么后續(xù)就會(huì)摻入了哨兵節(jié)點(diǎn)的值來(lái)比較，因此，n1 一開(kāi)始時(shí)需要指向頭節(jié)點(diǎn)。對(duì)于 n2 來(lái)說(shuō)，n2 = n1.next ，也就是 n2 在 n1 指向的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。接下來(lái)：當(dāng) n1.value == n2.value 時(shí)，則將 n1.next = n2.next ；當(dāng) n1.value != n2.value 時(shí)，則 n1 = n1.next 。? ? ?

????????循環(huán)的條件為：(n2 = n1.next) != null 。

代碼如下：

    //去重方法二(保留):雙指針
    public List removeDoublePointer(List list) {
        if (list == null) {
            return null;
        }

        //少于兩個(gè)節(jié)點(diǎn)，不存在重復(fù)的值
        if (list.sentry.next == null || list.sentry.next.next == null) {
            return null;
        }

        Node n1 = list.sentry.next;
        Node n2;

        while ((n2 = n1.next) != null) {

            if (n2.value == n1.value) {
                n1.next = n2.next;
            }else {
                n1 = n1.next;
            }
        }

        return list;
    }

? ? ? ? 需要注意的是，先得判斷對(duì)象是否為 null ；還有一種情況，當(dāng)節(jié)點(diǎn)少于兩個(gè)時(shí)，不存在重復(fù)的值的節(jié)點(diǎn)。

? ? ? ? 2.3?有序鏈表去重(不保留重復(fù)的節(jié)點(diǎn)) -?使用遞歸來(lái)實(shí)現(xiàn)

? ? ? ? 具體思路：先來(lái)考慮遞出的終止條件為：當(dāng) p == null 或者 p.next == null 的情況時(shí)，直接返回 p 該節(jié)點(diǎn)，因?yàn)楫?dāng) p.next == null 時(shí)，不存在有兩個(gè)重復(fù)值的節(jié)點(diǎn)，因此就沒(méi)有必要再繼續(xù)遞歸下去了。再來(lái)考慮遞出的兩種情況：當(dāng) p.value != p.next.value 時(shí)，沒(méi)有重復(fù)，則返回當(dāng)前節(jié)點(diǎn) p ，但是在此之前，需要對(duì) p.next 重新賦值，即重新調(diào)整 p.next?的指向；當(dāng) p.value == p.next.vaule 時(shí)，存在重復(fù)，則將該值的節(jié)點(diǎn)全部找出來(lái)，直到找到最后一個(gè)節(jié)點(diǎn)。循環(huán)的條件為： p.value == p.next.value ，循環(huán)結(jié)束后，得到的 p 就是最后一個(gè)重復(fù)值的節(jié)點(diǎn)，因?yàn)椴恍枰@個(gè)節(jié)點(diǎn)，則返回下一個(gè)節(jié)點(diǎn)。

代碼如下：

    //去重方法一(不保留):遞歸
    public List removeRepeat(List list) {
        Node temp = list.sentry;
        sentry = recursion(temp);
        return list;
    }

    public Node recursion(Node p) {
        if (p == null || p.next == null) {
            return p;
        }

        if (p.value != p.next.value) {
            p.next = recursion(p.next);
            return p;
        }else {
            while (p.value == p.next.value) {
                p = p.next;
            }
            return recursion(p.next);
        }

    }

? ? ? ? 同樣的，也需要先判斷該對(duì)象是否為 null ，否則容易報(bào)異常。

? ? ? ? 2.4?有序鏈表去重(不保留重復(fù)的節(jié)點(diǎn)) -?使用三指針來(lái)實(shí)現(xiàn)

? ? ? ? 具體思路：先定義三個(gè)指針，對(duì)于 p1 來(lái)說(shuō)：?一開(kāi)始時(shí)指向哨兵節(jié)點(diǎn)，假如不實(shí)現(xiàn)哨兵節(jié)點(diǎn)，則刪除不了當(dāng)鏈表中前幾個(gè)為重復(fù)值的節(jié)點(diǎn)(比如：1->1->1->2->null) ，因此，需要實(shí)現(xiàn)哨兵來(lái)完成該需求；對(duì)與 p2 來(lái)說(shuō)：一開(kāi)始時(shí)指向頭節(jié)點(diǎn)，即 p1.next；對(duì)于 p3 來(lái)說(shuō)：一開(kāi)始時(shí)指向頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，即 p2.next 。接下來(lái)，對(duì)于循環(huán)的兩種過(guò)程來(lái)分析：當(dāng) p2.value == p3.value 時(shí)，需要接著找到兩個(gè)節(jié)點(diǎn)的值不相等的時(shí)候，所以?xún)?nèi)層循環(huán)條件為：p2.value == p3.value 且 p3 != null，這里需要特別注意的是，千萬(wàn)不能丟了 p3 != null 的限制條件。跳出內(nèi)層循環(huán)是，就可能意味著找到了，則將 p1.next = p3 ；當(dāng) p2.value != p3.value 時(shí)，直接 p1 = p1.next 即可。外層循環(huán)的條件為：（(p2 = p1.next) != null 且?(p3 = p2.next) != null）

代碼如下：

    //去重方法二(不保留):三指針
    public List removeThreePointer(List list) {

        if (list == null) {
            return null;
        }

        Node n1 = list.sentry;
        Node n2 ;
        Node n3 ;
        while ((n2 = n1.next) != null && (n3 = n2.next) != null) {
            if (n2.value == n3.value) {
                while (n3 != null && n2.value == n3.value) {
                    n3 = n3.next;
                }
                n1.next = n3;
            }else {
                n1 = n1.next;
            }
        }
        return list;
    }

? ? ? ? 這里有個(gè)小技巧，對(duì)與 p2、p3 來(lái)說(shuō)，不著急賦值，在判斷條件的時(shí)候再進(jìn)行賦值，可以簡(jiǎn)略代碼量，提高可讀性。

? ? ? ? 3.0 合并升序鏈表

? ? ? ? 分為兩種情況：

? ? ? ? 一、合并兩個(gè)升序鏈表

? ? ? ? 使用迭代法實(shí)現(xiàn)合并鏈表、使用遞歸實(shí)現(xiàn)合并鏈表

? ? ? ? 二、合并多個(gè)升序鏈表

? ? ? ? 合并多個(gè)升序鏈表就是一個(gè)個(gè)合并兩個(gè)升序鏈表的情況，用遞歸來(lái)實(shí)現(xiàn)

? ? ? ? 3.1?合并升序鏈表(兩個(gè)鏈表)?- 迭代法

? ? ? ? 具體思路：對(duì)于兩個(gè)鏈表合并來(lái)說(shuō)，在各自的鏈表中分別定義一個(gè)指針，分別指向各自的頭節(jié)點(diǎn)。合并一條新的鏈表，定義一個(gè)指針指向哨兵節(jié)點(diǎn)。

代碼如下：

    //合并升序鏈表
    public static List combinedList(List l1,List l2) {
        if (l1 == null && l2 == null) {
            return null;
        } else if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }

        List newList = new List();
        Node node1 = l1.sentry.next;
        Node node2 = l2.sentry.next;
        Node p = newList.sentry;

        while (node1 != null && node2 != null) {

            if (node1.value < node2.value) {
                p.next = node1;
                node1 = node1.next;
            }else {
                p.next = node2;
                node2 = node2.next;
            }
            p = p.next;
        }

        if (node1 != null) {
            p.next = node1;
        }
        if (node2 != null) {
            p.next = node2;
        }
        return newList;
    }

????????

? ? ? ? 3.2?合并升序鏈表(兩個(gè)鏈表)?- 遞歸法

? ? ? ? 具體思路：先來(lái)考慮遞出的終止條件為：當(dāng) p1 == null 時(shí)，則直接返回 p2；當(dāng) p2 == null 時(shí)，則直接返回 p1。再來(lái)考慮遞出的過(guò)程：當(dāng) p1.value < p2.value 時(shí)，返回的節(jié)點(diǎn)為 p1 節(jié)點(diǎn)，在返回節(jié)點(diǎn)之前，需要將 p1.next 對(duì)該節(jié)點(diǎn)的重新調(diào)整指向下一個(gè)節(jié)點(diǎn)；當(dāng) p1.value >= p2.value 時(shí)，返回的節(jié)點(diǎn)為 p2 節(jié)點(diǎn)，同理，在返回該節(jié)點(diǎn)之前，需要將 p2.next 對(duì)該節(jié)點(diǎn)的重新調(diào)整指向下一個(gè)節(jié)點(diǎn)。

代碼如下：

     private Node combineRecursion(Node p1, Node p2) {
        if (p1 == null) {
            return p2;
        } else if (p2 == null ) {
            return p1;
        }

        if (p1.value < p2.value) {
            p1.next = combineRecursion(p1.next,p2);
            return p1;
        }else {
            p2.next = combineRecursion(p1,p2.next);
            return p2;
        }

     }

? ? ? ? 3.3 合并多個(gè)升序鏈表

? ? ? ? 具體思路：這是一個(gè)多路遞歸，在每一次的遞歸過(guò)程中，都可以看成有兩個(gè)升序鏈表進(jìn)行來(lái)合并。

代碼如下：

     //實(shí)現(xiàn)多個(gè)升序鏈表合并
    public List moreCombine(Node[] nodes) {
        List list = new List();
        list.sentry.next = moreCombineRecursion(nodes,0, nodes.length-1);
        return list;
    }

    private Node moreCombineRecursion(Node[] nodes,int i,int j) {

        if (j == 1) {
            return nodes[i];
        }
        int mid = (i + j) >>> 1;
        Node left = moreCombineRecursion(nodes,i,mid);
        Node right = moreCombineRecursion(nodes,mid+1,j);
        return combineRecursion(left,right);
    }

舉例畫(huà)圖分析：

? ? ? ? 對(duì)以上的流程圖簡(jiǎn)單分析：注意的是結(jié)束遞出的條件為：i == j 結(jié)束遞出，開(kāi)始回歸。回歸的是每一個(gè)鏈表的節(jié)點(diǎn)，最后集齊了兩個(gè)鏈表，需要通過(guò)利用兩個(gè)鏈表升序合并的返回進(jìn)行合并，可以用迭代法或者遞歸法。這只是其中的一小部分，不過(guò)每一個(gè)過(guò)程都是一樣的，就不多贅述了。

?

? ? ? ? 4.0 實(shí)現(xiàn)有序鏈表去重、合并升序鏈表的完整代碼

?

import java.util.Iterator;

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

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

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

    public List() {
        sentry = new Node(-1,null);
    }

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

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

    //重寫(xiě)迭代器
    @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 value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    //去重方法二(保留):雙指針
    public List removeDoublePointer(List list) {
        if (list == null) {
            return null;
        }

        //少于兩個(gè)節(jié)點(diǎn)，不存在重復(fù)的值
        if (list.sentry.next == null || list.sentry.next.next == null) {
            return null;
        }

        Node n1 = list.sentry.next;
        Node n2;

        while ((n2 = n1.next) != null) {

            if (n2.value == n1.value) {
                n1.next = n2.next;
            }else {
                n1 = n1.next;
            }
        }

        return list;
    }


    //去重方法一(保留):遞歸
    public List removeRecursion(List list) {
        Node sentry1 = list.sentry;
        sentry = recursion1(sentry1);
        return list;
    }

    private Node recursion1(Node p) {

        if (p == null || p.next == null) {
            return p;
        }
        if (p.value == p.next.value) {
            return recursion1(p.next);
        }else {
            p.next = recursion1(p.next);
            return p;
        }

    }



    //去重方法一(不保留):遞歸
    public List removeRepeat(List list) {
        Node temp = list.sentry;
        sentry = recursion(temp);
        return list;
    }

    public Node recursion(Node p) {
        if (p == null || p.next == null) {
            return p;
        }

        if (p.value != p.next.value) {
            p.next = recursion(p.next);
            return p;
        }else {
            while (p.value == p.next.value) {
                p = p.next;
            }
            return recursion(p.next);
        }

    }


    //去重方法二(不保留):三指針
    public List removeThreePointer(List list) {

        if (list == null) {
            return null;
        }

        Node n1 = list.sentry;
        Node n2 ;
        Node n3 ;
        while ((n2 = n1.next) != null && (n3 = n2.next) != null) {
            if (n2.value == n3.value) {
                while (n3 != null && n2.value == n3.value) {
                    n3 = n3.next;
                }
                n1.next = n3;
            }else {
                n1 = n1.next;
            }
        }
        return list;
    }


    //合并升序鏈表
    public static List combinedList(List l1,List l2) {
        if (l1 == null && l2 == null) {
            return null;
        } else if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }

        List newList = new List();
        Node node1 = l1.sentry.next;
        Node node2 = l2.sentry.next;
        Node p = newList.sentry;

        while (node1 != null && node2 != null) {

            if (node1.value < node2.value) {
                p.next = node1;
                node1 = node1.next;
            }else {
                p.next = node2;
                node2 = node2.next;
            }
            p = p.next;
        }

        if (node1 != null) {
            p.next = node1;
        }
        if (node2 != null) {
            p.next = node2;
        }
        return newList;
    }

    //合并鏈表:遞歸實(shí)現(xiàn)
    public List combineList(List list2) {
        List newList = new List();
        Node p1 = this.sentry.next;
        Node p2 = list2.sentry.next;
        Node p = combineRecursion(p1,p2);
        newList.sentry.next = p;
        return newList;
    }

     private Node combineRecursion(Node p1, Node p2) {
        if (p1 == null) {
            return p2;
        } else if (p2 == null ) {
            return p1;
        }

        if (p1.value < p2.value) {
            p1.next = combineRecursion(p1.next,p2);
            return p1;
        }else {
            p2.next = combineRecursion(p1,p2.next);
            return p2;
        }

     }

     //實(shí)現(xiàn)多個(gè)升序鏈表合并
    public List moreCombine(Node[] nodes) {
        List list = new List();
        list.sentry.next = moreCombineRecursion(nodes,0, nodes.length-1);
        return list;
    }

    private Node moreCombineRecursion(Node[] nodes,int i,int j) {

        if (j == i) {
            return nodes[i];
        }
        int mid = (i + j) >>> 1;
        Node left = moreCombineRecursion(nodes,i,mid);
        Node right = moreCombineRecursion(nodes,mid+1,j);
        return combineRecursion(left,right);
    }

}

?????????

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-752788.html

到了這里，關(guān)于Java 算法篇-鏈表的經(jīng)典算法：有序鏈表去重、合并多個(gè)有序鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！