【剣指Offer学習】【面接問題26:複雑チェーンのコピー】【考え方】

タイトル:
複雑なチェーンテーブル(各ノードにノード値と2つのポインタがあり、1つは次のノードを指し、もう1つの特殊なポインタは任意のノードを指す)を入力し、コピー後の複雑なチェーンテーブルのheadを返します.(出力結果ではパラメータのノード参照を返さないでください.そうしないと、問題判定プログラムは直接空に戻ります)
 
考え方:

元のチェーンテーブルの各ノードNから対応するN’

を作成する.

コピー後のノードを元のノード後

に接続する.
元のチェーンテーブル:A->B->C->D->E
コピーされたチェーンテーブル:A->A->B->B->C->C->D->E->E

コピーされたノードのrandomポインタを設定します.

AのrandomポインタがCを指す場合、A’のrandomポインタがC’を指す
その対応コピーされたA’はAのnextが指すノードであり,同様にC’もCのnextが指すノードである.

は2つのチェーンテーブルに分割され、偶数の位置のノードを取り、接続すると複製された新しいチェーンテーブル

である.
 
コード:

package        26;

/**
 *         （         ，      ，
 *          ，               ），
 *              head。
 * （  ，                  ，            ）
 * @author Administrator
 *
 */
class RandomListNode {
    int label;
    RandomListNode next = null;		//        
    RandomListNode random = null;	// 

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

public class Demo {

	/**
	 * 1、            N       N’
	 * 2、             
	 *     ：A -> B -> C -> D -> E
	 *       ：A -> A’ -> B -> B’ -> C -> C’ -> D -> D’ -> E -> E’
	 * 3、           random   。
	 *  ，A   random      C，   A’   random      C’
	 *          A’  A   next      ，   C’   C   next      。
	 * 4、       ，         ，              
	 * 
	 * @param pHead
	 * @return
	 */
	public RandomListNode Clone(RandomListNode pHead) {
		if (pHead == null) {
			return null;
		}
		
		RandomListNode head = new RandomListNode(pHead.label);
		RandomListNode temp = head;
		
		while (pHead.next != null) {
			//      next   ，      
			temp.next = new RandomListNode(pHead.next.label);
			//            random       ，  
			if (pHead.random != null) {
				temp.random = new RandomListNode(pHead.random.label);
			}
			pHead = pHead.next;
			temp = temp.next;
		}
		return head;
	}

	/**
     *       
     *
     * @param head      
     */
    public static void printList(RandomListNode head) {
        while (head != null) {
            System.out.print(head.label + "->");
            head = head.next;
        }
        System.out.println("null");
    }
	
	public static void main(String[] args) {
		//     		-----------------
	    //         \|/              |
	    //  1-------2-------3-------4-------5
	    //  |       |      /|\             /|\
	    //  --------+--------               |
	    //          -------------------------
	    RandomListNode head = new RandomListNode(1);
	    head.next = new RandomListNode(2);
	    head.next.next = new RandomListNode(3);
	    head.next.next.next = new RandomListNode(4);
	    head.next.next.next.next = new RandomListNode(5);
	    head.random = head.next.next;
	    head.next.random = head.next.next.next.next.next;
	    head.next.next.next.random = head.next;
	    printList(head);
	}
}