文章簡(jiǎn)述

在本次的文章中，按照個(gè)人的刷題計(jì)劃，會(huì)分享關(guān)于鏈表的 3 道簡(jiǎn)單級(jí)別的算法題（可是依然感覺(jué)不簡(jiǎn)單）

但是不要緊，從本篇文章開(kāi)始分享的算法題個(gè)人都會(huì)把關(guān)于這道題的全部代碼寫(xiě)出來(lái)，并用debug的形式，分解每一步來(lái)整理出來(lái)。

通過(guò)還原題目場(chǎng)景，用 debug 調(diào)試的方式去分析，印象更加深刻些。

本篇文章中共有 3 道題目。

一，合并兩個(gè)有序鏈表

1.1 題目分析

看到這道題的時(shí)候，第一反應(yīng)就是先將兩個(gè)鏈表合并，然后再排序。嗯。。。不用想，絕對(duì)的暴力寫(xiě)法。

或者是循環(huán)兩個(gè)鏈表，然后兩兩相比較，就像：

for(){
  for(){
    if(){}
  }
}

好吧，其實(shí)這道題精華在于可以使用遞歸，這個(gè)。。。來(lái)個(gè)草圖簡(jiǎn)單描述下。

第一步：

兩個(gè)鏈表的首節(jié)點(diǎn)進(jìn)行比較

兩個(gè)節(jié)點(diǎn)相等，則使 L2 鏈表【1】，和 L1 鏈表的【2】進(jìn)行比較

注意：

L1節(jié)點(diǎn)【1】和L2節(jié)點(diǎn)【1】比較完成后，需要修改1.next指針，以指向它的下個(gè)節(jié)點(diǎn)。

第二步：

現(xiàn)在我們獲取到了 L2 鏈表【1】，那它的 next 指向誰(shuí)？也就是 L2 鏈表【1】去和 L1 鏈表的【2】進(jìn)行比較。

比較完成后，L2 鏈表【1】的 next 就指向了 L1 鏈表【2】，接著以此類(lèi)推。

L2 鏈表【3】去和 L1 鏈表【4】比較。

最后 L1 鏈表【4】和 L2 鏈表【4】比較。

全部比較完成后，整個(gè)鏈表就已經(jīng)排序完成了。

遞歸的方式就在于，兩兩節(jié)點(diǎn)進(jìn)行比較，當(dāng)有一個(gè)鏈表為null時(shí)，表示其中一個(gè)鏈表已經(jīng)遍歷完成，那就需要終止遞歸，并將比較結(jié)果進(jìn)行返回。

可能只是單純的畫(huà)圖并不好理解，下面用代碼 debug 的方式去分析，還請(qǐng)耐心往下看。

1.2 代碼分析

按照題意需要先創(chuàng)建 2 個(gè)單鏈表，具體的創(chuàng)建方式可以參考本人的第一篇文章《手寫(xiě)單鏈表基礎(chǔ)之增，刪，查！附贈(zèng)一道鏈表題》。不多說(shuō)，先初始化節(jié)點(diǎn)對(duì)象。

class ListNode {
    /**
     * 數(shù)據(jù)域
     */
    int val;
    /**
     * 下一個(gè)節(jié)點(diǎn)指針
     */
    ListNode next;

    ListNode() {
    }
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}

定義新增鏈表方法。

 public ListNode add(ListNode node) {
        // 1，定義輔助指針
        ListNode temp = nodeHead;
        // 2，首先判斷當(dāng)前節(jié)點(diǎn)是否為最后節(jié)點(diǎn)
        if (null == temp.next) {
            // 當(dāng)前節(jié)點(diǎn)為最后節(jié)點(diǎn)
            temp.next = node;
            return nodeHead;
        }
        // 3，循環(huán)遍歷節(jié)點(diǎn)，如果當(dāng)前節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)不為空，表示還有后續(xù)節(jié)點(diǎn)
        while (null != temp.next) {
            // 否則將指針后移
            temp = temp.next;
        }
        // 4，遍歷結(jié)束，將最后節(jié)點(diǎn)的指針指向新添加的節(jié)點(diǎn)
        temp.next = node;
        return nodeHead.next;
    }

接著創(chuàng)建 2 個(gè)鏈表。

 /**
         * 定義L1鏈表
         */
        ListNode l11 = new ListNode(1);
        ListNode l12 = new ListNode(2);
        ListNode l13 = new ListNode(4);

        MergeLinkedList l1 = new MergeLinkedList();
        l1.add(l11);
        l1.add(l12);
        /**
         * 返回新增完的L1鏈表
         */
        ListNode add1 = l1.add(l13);

        /**
         * 定義L2鏈表
         */
        ListNode l21 = new ListNode(1);
        ListNode l22 = new ListNode(3);
        ListNode l23 = new ListNode(4);

        MergeLinkedList l2 = new MergeLinkedList();
        l2.add(l21);
        l2.add(l22);
        /**
         * 返回L2鏈表
         */
        ListNode add2 = l2.add(l23);

我們先把上述圖中使用遞歸的代碼貼出來(lái)。

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        /**
         * 如果L1鏈表為null，終止遞歸
         */
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        /**
         * 按照?qǐng)D中的描述，兩兩比較鏈表的節(jié)點(diǎn)
         */
        if (l1.val <= l2.val) {
            /**
             * L1的節(jié)點(diǎn)比L2的小，按照?qǐng)D中就是需要比較L1鏈表的下個(gè)節(jié)點(diǎn)
             * l1.next 就是指當(dāng)比較出節(jié)點(diǎn)大小后，需要修改指針的指引，將整個(gè)鏈表全部串聯(lián)起來(lái)
             */
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            /**
             * 同理，與上個(gè)if判斷一樣
             */
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

1.3 debug 調(diào)試

1.3.1 L1 鏈表已經(jīng)創(chuàng)建完成，同理 L2 也被創(chuàng)建完成。

1.3.2 比較兩個(gè)鏈表的首節(jié)點(diǎn)

注意：

l1.next是指向遞歸方法的，也就是上圖中我們描述的l1鏈表【1】指向了l2鏈表【1】，但是L2鏈表【1】又指向誰(shuí)？開(kāi)始進(jìn)入遞歸

1.3.3 如上圖，開(kāi)始比較 L2 鏈表【1】與 L1 鏈表的【2】

1.3.4 比較 L1 鏈表【2】與 L2 鏈表【3】

1.3.5 后面操作是一樣的，下面就直接展示最后兩個(gè)節(jié)點(diǎn)比較

這里已經(jīng)到最后兩個(gè)節(jié)點(diǎn)的比較。

這個(gè)時(shí)候 L1 鏈表先遍歷完成，需要終止遞歸，返回 L2 鏈表。為什么返回 L2 鏈表？直接看圖。

因?yàn)樽詈笠徊奖容^的是 L1 鏈表【4】和 L2 鏈表【4】，也就是說(shuō) L2 鏈表【4】是最后的節(jié)點(diǎn)，如果返回 L1 鏈表，那 L2 鏈表【4】就會(huì)被丟棄，可參考上面圖解的最后一張。

重點(diǎn)來(lái)了！！！

L1 鏈表已經(jīng)遍歷完成，開(kāi)始觸發(fā)遞歸將比較的結(jié)果逐次返回。

這是不是我們最后 L1 鏈表【4】和 L2 鏈表【4】比較的那一步，是不是很明顯，l1.next 指向了 l1 的節(jié)點(diǎn)【4】，而 L1 節(jié)點(diǎn)也就是它最后的節(jié)點(diǎn)【4】，和我們那上面圖解中最后的結(jié)論一樣。

再接著執(zhí)行下一步返回。

L2 鏈表的【3】指向了 L1 鏈表的【4】

同理，按照之前遞歸的結(jié)果以此返回就可以了，那我們來(lái)看下最終的排序結(jié)果。

二，刪除排序鏈表中的重復(fù)元素

2.1 題目分析

初次看這道題好像挺簡(jiǎn)單的，這不就是個(gè)人之前寫(xiě)的第一篇文章里面，刪除鏈表節(jié)點(diǎn)嗎！

仔細(xì)審題其實(shí)這道題要更簡(jiǎn)單些，因?yàn)轭}中已說(shuō)明是一個(gè)排序鏈表，因此我們只需要將當(dāng)前節(jié)點(diǎn)與下一個(gè)節(jié)點(diǎn)進(jìn)行比較，如果相等則直接修改 next 指針即可。

2.1 代碼分析

同樣是鏈表的定義，與上面第一題中的創(chuàng)建是一樣的，只不過(guò)我們是需要再重新創(chuàng)建一個(gè)單鏈表。

				ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(1);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(4);
        ListNode l6 = new ListNode(5);

        NodeFun nodeFun = new NodeFun();
        nodeFun.add(l1);
        nodeFun.add(l2);
        nodeFun.add(l3);
        nodeFun.add(l4);
        nodeFun.add(l5);
        ListNode listNode = nodeFun.add(l6);

創(chuàng)建完成后，接著看去重復(fù)的代碼。

public ListNode deleteDuplicates(ListNode head) {
        /**
         * 定義輔助指針
         */
        ListNode temp = head;
        /**
         * 判斷當(dāng)前節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)不能為空，因?yàn)槭切枰獙?dāng)前節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)進(jìn)行比較的
         */
        while (temp != null && temp.next != null) {
            /**
             * 如果節(jié)點(diǎn)值相同
             */
            if (temp.val == temp.next.val) {
                /**
                 * 表示當(dāng)前節(jié)點(diǎn)與下一個(gè)節(jié)點(diǎn)的值相同，則移動(dòng)指針
                 */
                temp.next = temp.next.next;
            } else {
                /**
                 * 必須移動(dòng)指針，否則會(huì)產(chǎn)生死循環(huán)
                 */
                temp = temp.next;
            }
        }
        return head;
    }
}

2.2 debug 調(diào)試

2.2.1 按照初始化的鏈表，應(yīng)該是首節(jié)點(diǎn)【1】和第二個(gè)節(jié)點(diǎn)【1】進(jìn)行比較。

不用說(shuō)兩個(gè)節(jié)點(diǎn)是相等的，那下一步進(jìn)入 if 判斷，就是修改指針的指向。

此時(shí)第二個(gè)節(jié)點(diǎn)【1】已經(jīng)沒(méi)有被 next 指引了，就會(huì)被 GC 回收掉。

2.2.2 下一步就是節(jié)點(diǎn)【1】和節(jié)點(diǎn)【3】進(jìn)行比較

兩個(gè)節(jié)點(diǎn)不相等，進(jìn)入 else 將輔助指針移動(dòng)到下個(gè)節(jié)點(diǎn)。

那么剩下的節(jié)點(diǎn)判斷也都是一樣的，我們最后看下打印的結(jié)果。

三，環(huán)形鏈表

3.1 題目分析

如果這個(gè)鏈表里面有環(huán)，其中一個(gè)節(jié)點(diǎn)必然是被指針指引了一次或者多次（如果有多個(gè)環(huán)的話(huà)）。因此個(gè)人當(dāng)時(shí)簡(jiǎn)單的做法就是遍歷鏈表，把遍歷過(guò)的節(jié)點(diǎn)對(duì)象保存到 HashSet 中，每遍歷下一個(gè)節(jié)點(diǎn)時(shí)去 HashSet 中比對(duì)，存在就表示有環(huán)。

而這道題沒(méi)有設(shè)置過(guò)多的要求，只要有環(huán)返回 boolean 就好。

還有一種巧妙的寫(xiě)法，使用快慢指針的思想。

這種方式大致意思就是說(shuō)，快慢指針比作龜兔賽跑，兔子跑的快，如果存在環(huán)那么兔子就會(huì)比烏龜先跑進(jìn)環(huán)中。那么它們就會(huì)在某個(gè)節(jié)點(diǎn)上相遇，相遇了也就說(shuō)明鏈表是有環(huán)的。

那么，你們問(wèn)題是不是來(lái)了？這不公平啊，【兔子】本來(lái)就比【烏龜】跑的快，那咋兔子還先跑了。

試想，如果它倆都在一個(gè)節(jié)點(diǎn)上跑，那它們從開(kāi)始不就是相遇了，因?yàn)槲覀兾覀兪窃O(shè)定如果在一個(gè)節(jié)點(diǎn)上相遇，表示鏈表是有環(huán)的。所以，這不是“不打自招“了！

比賽開(kāi)始，這【兔子大哥】有點(diǎn)猛啊，一下跑兩個(gè)節(jié)點(diǎn)。

果然，有情人終成眷屬，它們相遇了。

3.2 代碼分析

這次創(chuàng)建鏈表的時(shí)候，就不能單純是個(gè)單鏈表了，還得加個(gè)環(huán)。

 		ListNode l1 = new ListNode(3);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(0);
        ListNode l4 = new ListNode(-4);

        /**
         * 給主角加個(gè)環(huán)
         */
        l4.next = l2;

        NodeFun nodeFun = new NodeFun();
        nodeFun.add(l1);
        nodeFun.add(l2);
        nodeFun.add(l3);
        ListNode listNode = nodeFun.add(l4);

那就一起來(lái)找環(huán)吧。

public boolean hasCycle(ListNode head) {
        ListNode temp = head;
        if(null == head){
            // 為空表示沒(méi)有環(huán)
            return false;
        }
        // 1，set集合保存遍歷過(guò)的節(jié)點(diǎn)，如果新的節(jié)點(diǎn)已經(jīng)在set中，表示存在環(huán)
        // 2，使用快慢指針的思想
        // 定義慢指針
        ListNode slow = head;
        // 定義快指針
        ListNode fast = head.next;
        // 循環(huán)，只要2個(gè)指針不重合，就一直循環(huán)
        while(slow != fast){
            // 如果2個(gè)指針都到達(dá)尾節(jié)點(diǎn)，表示沒(méi)有環(huán)
            if(fast == null || fast.next == null){
                return false;
            }
            // 否則就移動(dòng)指針
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }