【算法】解題總結：劍指 Offer 35 複雜連結清單的複制、劍指 Offer 76 删除連結清單中重複的結點

JZ35 複雜連結清單的複制

（較難）

題目

描述 輸入一個複雜連結清單（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針random指向一個随機節點），請對此連結清單進行深拷貝，并傳回拷貝後的頭結點。（注意，輸出結果中請不要傳回參數中的節點引用，否則判題程式會直接傳回空）。 下圖是一個含有5個結點的複雜連結清單。圖中實線箭頭表示next指針，虛線箭頭表示random指針。為簡單起見，指向null的指針沒有畫出。

示例: 輸入:{1,2,3,4,5,3,5,#,2,#} 輸出:{1,2,3,4,5,3,5,#,2,#} 解析:我們将連結清單分為兩段，前半部分{1,2,3,4,5}為ListNode，後半部分{3,5,#,2,#}是随機指針域表示。 以上示例前半部分可以表示連結清單為的ListNode:1->2->3->4->5 後半部分，3，5，#，2，#分别的表示為 1的位置指向3，2的位置指向5，3的位置指向null，4的位置指向2，5的位置指向null 如下圖:

示例

輸入：

{1,2,3,4,5,3,5,#,2,#}

傳回值：

{1,2,3,4,5,3,5,#,2,#}

思路

本題感覺也沒有什麼難度，不知道為什麼劃分為 “較難” 題型，本題的輸入雖然看起來是輸入了兩個連結清單長度數量的元素，但是在背景校驗時其實就是傳了一個連結清單而已（下文也進行了本題背景機制的測試），而其中每個結點除最後一個結點外都有 next 結點；可以有 random 結點，也可以沒有。而本題要求深拷貝連結清單，也就是将所有引用資料類型都進行真正的複制，而對于本連結清單來說，要将所有結點都複制一遍，用一個新建立的頭結點儲存後續結果，同時既要兼顧在建立中維護 next 結點、random 結點的指向，而要實作這些，隻需周遊一次連結清單即可，即時間複雜度為 O(n)，下面為代碼實作。

實作

class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}

public class JZ35複雜連結清單的複制 {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }

        RandomListNode tmp = pHead; //tmp 指向第一個結點
        RandomListNode head = new RandomListNode(pHead.label); //結果連結清單
        RandomListNode cur = head;
        while (tmp.next != null) {
            cur.next = new RandomListNode(tmp.next.label);

            if (tmp.random != null) {
                cur.random = new RandomListNode(tmp.random.label);
            }
            cur = cur.next;
            tmp = tmp.next;
        }

        return head;
    }
}      

（下面這裡是當時比較好奇這道題的機制，是輸入一個連結清單，還是真就是連 random 鍊的指向也輸入進去，發現，确實是輸入一個連結清單，是以，也沒什麼可以優化的了）

JZ76 删除連結清單中重複的結點

（中等）

題目

描述

在一個排序的連結清單中，存在重複的結點，請删除該連結清單中重複的結點，重複的結點不保留，傳回連結清單頭指針。 例如，連結清單1->2->3->3->4->4->5 處理後為 1->2->5。

示例1

輸入：

{1,2,3,3,4,4,5}

傳回值：

{1,2,5}

示例2

輸入：

{1,1,1,8}

傳回值：

{8}

思路

我在解決此題時用的是貪心思想，首先建立一個結果連結清單的頭結點，用來存儲最終結果，局部最優就是每次都向此結果連結清單中加入一個值不重複的結點，而全局最優就是最終結果連結清單中都不會有重複的結點，雖然聽上去是廢話，但這确實是一種貪心思想，而此思想的核心問題，就在于其局部最優在本題中如何實作，我的方法是，将對原連結清單的一次周遊過程分為三種情況（由于第一個結點與最後一個結點分别沒有前驅與後繼，是以這兩種情況要特殊考慮，而中間結點的情況都可以統一判斷）：

• 第 1 次周遊：如果第一個結點值與第二個結點值不相等，那麼就應将第一個結點加入結果連結清單；
• 第 2 至第 n-1 次周遊：如果一個結點的值與它的前一個結點的值與後一個結點的值都不相等，那麼就應該将此結點的值加入結果連結清單；
• 第 n 次周遊：如果最後一個結點與前一個結點值不相等，那麼就應該将此結點的值加入結果連結清單。

實作

public class JZ76删除連結清單中重複的結點 {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return pHead;
        }

        ListNode cur = pHead;
        ListNode res = new ListNode(-1);
        ListNode tmp = res;
        ListNode pre = null; //上一次的結果

        while (cur.next != null) {
            if ((pre == null && cur.val != cur.next.val) //第 1 次周遊
                    || (pre != null && cur.val != pre.val && cur.val != cur.next.val) //2 ~ n-1 次周遊
            ) {
                res.next = new ListNode(cur.val);
                res = res.next;
            }

            pre = cur;
            cur = cur.next;
        }

        if (cur.val != pre.val) { //第 n 次周遊
            res.next = new ListNode(cur.val);
        }

        return tmp.next;
    }
}