復(fù)雜鏈表的復(fù)制

題目：請實現(xiàn)函數(shù) ComplexListNode clone(ComplexListNode head)，復(fù)制一個復(fù)雜鏈表。在復(fù)雜鏈表中，每個結(jié)點除了有一個 next 域指向下一個結(jié)點外，還有一個 sibling 指向鏈表中的任意結(jié)點或者 null。

結(jié)點結(jié)構(gòu)定義：

public static class ComplexListNode {
    int value;
    ComplexListNode next;
    ComplexListNode sibling;
}

解題思路：

圖 4.8 是一個含有 5 個結(jié)點的復(fù)雜鏈表。圖中實線箭頭表示 next 指針，虛線箭頭表示 sibling 指針。為簡單起見，指向 null 的指針沒有畫出。

http://wiki.jikexueyuan.com/project/for-offer/images/33.png" alt="" />

在不用輔助空間的情況下實現(xiàn) O(n)的時間效率。

第一步：仍然是根據(jù)原始鏈表的每個結(jié)點N 創(chuàng)建對應(yīng)的 N’。把 N’鏈接在N的后面。圖 4.8 的鏈表經(jīng)過這一步之后的結(jié)構(gòu)，如圖 4.9 所示。

http://wiki.jikexueyuan.com/project/for-offer/images/34.png" alt="" />

第二步：設(shè)置復(fù)制出來的結(jié)點的 sibling。假設(shè)原始鏈表上的 N 的 sibling 指向結(jié)點 S，那么其對應(yīng)復(fù)制出來的 N’是 N的 pext 指向的結(jié)點，同樣 S’也是 S 的 next 指向的結(jié)點。設(shè)置 sibling 之后的鏈表如圖 4.10 所示。

http://wiki.jikexueyuan.com/project/for-offer/images/35.png" alt="" />

第三步：把這個長鏈表拆分成兩個鏈表。把奇數(shù)位置的結(jié)點用 next 鏈接起來就是原始鏈表，把偶數(shù)位置的結(jié)點用 next 鏈接起來就是復(fù)制 出來的鏈表。圖 4.10 中的鏈表拆分之后的兩個鏈表如圖 4.11 所示。

http://wiki.jikexueyuan.com/project/for-offer/images/36.png" alt="" />

代碼實現(xiàn)：

public class Test26 {
    /**
     * 復(fù)雜鏈表結(jié)點
     */
    public static class ComplexListNode {
        int value;
        ComplexListNode next;
        ComplexListNode sibling;
    }
    /**
     * 實現(xiàn)函復(fù)制一個復(fù)雜鏈表。在復(fù)雜鏈表中，每個結(jié)點除了有一個next字段指向下一個結(jié)點外，
     * 還有一個sibling字段指向鏈表中的任意結(jié)點或者NULL
     *
     * @param head 鏈表表頭結(jié)點
     * @return 復(fù)制結(jié)點的頭結(jié)點
     */
    public static ComplexListNode clone(ComplexListNode head) {
        // 如果鏈表為空就直接返回空
        if (head == null) {
            return null;
        }
        // 先復(fù)制結(jié)點
        cloneNodes(head);
        // 再鏈接sibling字段
        connectNodes(head);
        // 將整個鏈表拆分，返回復(fù)制鏈表的頭結(jié)點
        return reconnectNodes(head);
    }
    /**
     * 復(fù)制一個鏈表，并且將復(fù)制后的結(jié)點插入到被復(fù)制的結(jié)點后面，只鏈接復(fù)制結(jié)點的next字段
     *
     * @param head 待復(fù)制鏈表的頭結(jié)點
     */
    public static void cloneNodes(ComplexListNode head) {
        // 如果鏈表不空，進行復(fù)制操作
        while (head != null) {
            // 創(chuàng)建一個新的結(jié)點
            ComplexListNode tmp = new ComplexListNode();
            // 將被復(fù)制結(jié)點的值傳給復(fù)制結(jié)點
//            tmp.value = head.value;
            ///////////////////////////////////////////////////////////////////////////////////////////
            // TODO 此處為了做測試，讓復(fù)制結(jié)點的值都增加了100，如果不需要可以將下面一個行注釋掉，打開上一行。
            tmp.value = head.value + 100;
            ///////////////////////////////////////////////////////////////////////////////////////////
            // 復(fù)制結(jié)點的next指向下一個要被復(fù)制的結(jié)點
            tmp.next = head.next;
            // 被復(fù)制結(jié)點的next指向復(fù)制結(jié)點
            head.next = tmp;
            // 到些處就已經(jīng)完成了一個結(jié)點的復(fù)制并且插入到被復(fù)制結(jié)點的后面
            // heed指向下一個被復(fù)制結(jié)點的位置
            head = tmp.next;
        }
    }
    /**
     * 設(shè)置復(fù)制結(jié)點的sibling字段
     *
     * @param head 鏈表的頭結(jié)
     */
    public static void connectNodes(ComplexListNode head) {
        // 如鏈表不為空
        while (head != null) {
            // 當(dāng)前處理的結(jié)點sibling字段不為空，則要設(shè)置其復(fù)制結(jié)點的sibling字段
            if (head.sibling != null) {
                // 復(fù)制結(jié)點的sibling指向被復(fù)制結(jié)點的sibling字段的下一個結(jié)點
                // head.next：表求復(fù)制結(jié)點，
                // head.sibling：表示被復(fù)制結(jié)點的sibling所指向的結(jié)點，
                // 它的下一個結(jié)點就是它的復(fù)制結(jié)點
                head.next.sibling = head.sibling.next;
            }
            // 指向下一個要處理的復(fù)制結(jié)點
            head = head.next.next;
        }
    }
    /**
     * 剛復(fù)制結(jié)點和被復(fù)制結(jié)點拆開，還原被復(fù)制的鏈表，同時生成監(jiān)制鏈表
     *
     * @param head 鏈表的頭結(jié)點
     * @return 復(fù)制鏈表的頭結(jié)點
     */
    public static ComplexListNode reconnectNodes(ComplexListNode head) {
        // 當(dāng)鏈表為空就直接返回空
        if (head == null) {
            return null;
        }
        // 用于記錄復(fù)制鏈表的頭結(jié)點
        ComplexListNode newHead = head.next;
        // 用于記錄當(dāng)前處理的復(fù)制結(jié)點
        ComplexListNode pointer = newHead;
        // 被復(fù)制結(jié)點的next指向下一個被復(fù)制結(jié)點
        head.next = newHead.next;
        // 指向新的被復(fù)制結(jié)點
        head = head.next;
        while (head != null) {
            // pointer指向復(fù)制結(jié)點
            pointer.next = head.next;
            pointer = pointer.next;
            // head的下一個指向復(fù)制結(jié)點的下一個結(jié)點，即原來鏈表的結(jié)點
            head.next = pointer.next;
            // head指向下一個原來鏈表上的結(jié)點
            head = pointer.next;
        }
        // 返回復(fù)制鏈表的頭結(jié)點
        return newHead;
    }
    /**
     * 輸出鏈表信息
     *
     * @param head 鏈表頭結(jié)點
     */
    public static void printList(ComplexListNode head) {
        while (head != null) {
            System.out.print(head.value + "->");
            head = head.next;
        }
        System.out.println("null");
    }
    /**
     * 判斷兩個鏈表是否是同一個鏈表，不是值相同
     *
     * @param h1 鏈表頭1
     * @param h2 鏈表頭2
     * @return true：兩個鏈表是同一個鏈表，false：不是
     */
    public static boolean isSame(ComplexListNode h1, ComplexListNode h2) {
        while (h1 != null && h2 != null) {
            if (h1 == h2) {
                h1 = h1.next;
                h2 = h2.next;
            } else {
                return false;
            }
        }
        return h1 == null && h2 == null;
    }
    public static void main(String[] args) {
        //          -----------------
        //         \|/              |
        //  1-------2-------3-------4-------5
        //  |       |      /|\             /|\
        //  --------+--------               |
        //          -------------------------
        ComplexListNode head = new ComplexListNode();
        head.value = 1;
        head.next = new ComplexListNode();
        head.next.value = 2;
        head.next.next = new ComplexListNode();
        head.next.next.value = 3;
        head.next.next.next = new ComplexListNode();
        head.next.next.next.value = 4;
        head.next.next.next.next = new ComplexListNode();
        head.next.next.next.next.value = 5;
        head.sibling = head.next.next;
        head.next.sibling = head.next.next.next.next.next;
        head.next.next.next.sibling = head.next;
        ComplexListNode tmp = head;
        printList(head);
        ComplexListNode newHead = clone(head);
        printList(head);
        System.out.println(isSame(head, tmp));
        printList(newHead);
        System.out.println(isSame(head, newHead));
        // 有指向自身的情況
        //          -----------------
        //         \|/              |
        //  1-------2-------3-------4-------5
        //         |       | /|\           /|\
        //         |       | --             |
        //         |------------------------|
        ComplexListNode head2 = new ComplexListNode();
        head2.value = 1;
        head2.next = new ComplexListNode();
        head2.next.value = 2;
        head2.next.next = new ComplexListNode();
        head2.next.next.value = 3;
        head2.next.next.next = new ComplexListNode();
        head2.next.next.next.value = 4;
        head2.next.next.next.next = new ComplexListNode();
        head2.next.next.next.next.value = 5;
        head2.next.sibling = head2.next.next.next.next;
        head2.next.next.next.sibling = head2.next.sibling;
        head2.next.next.sibling = head2.next.next;
        System.out.println("\n");
        tmp = head2;
        printList(head2);
        ComplexListNode newHead2 = clone(head2);
        printList(head2);
        System.out.println(isSame(head2, tmp));
        printList(newHead2);
        System.out.println(isSame(head2, newHead2));
        ComplexListNode head3 = new ComplexListNode();
        head3.value = 1;
        System.out.println("\n");
        tmp = head3;
        printList(head3);
        ComplexListNode newHead3 = clone(head3);
        printList(head3);
        System.out.println(isSame(head3, tmp));
        printList(newHead3);
        System.out.println(isSame(head3, newHead3));
        System.out.println("\n");
        ComplexListNode head4 = clone(null);
        printList(head4);
    }
}

運行結(jié)果：

注意：劃紅線部分是為了區(qū)分原鏈表和復(fù)制鏈表，具體還原見代碼注釋。

http://wiki.jikexueyuan.com/project/for-offer/images/37.png" alt="" />