剣指offer第2面試験問題35:複雑なチェーンテーブルの複製(java)
タイトルの説明:複雑なチェーンテーブル(各ノードにノード値があり、2つのポインタがあり、1つは次のノードを指し、もう1つの特殊なポインタは任意のノードを指す)を入力し、コピー後の複雑なチェーンテーブルのheadを返します.(出力結果ではパラメータのノード参照を返さないでください.そうしないと、問題判定プログラムは直接空に戻ります)
分析:構想1:元のチェーンテーブルのノードをコピーして、要素チェーンテーブルのヘッダノードで各ノードのrandomを探し始めます.毎回最初から探して接続するので、時間の複雑さはo(n*n)構想2:空間で時間を交換します.mapマッピングテーブルを作成します.
分析:構想1:元のチェーンテーブルのノードをコピーして、要素チェーンテーブルのヘッダノードで各ノードのrandomを探し始めます.毎回最初から探して接続するので、時間の複雑さはo(n*n)構想2:空間で時間を交換します.mapマッピングテーブルを作成します.
/**
*
*/
public class CopyList {
public RandomListNode Clone(RandomListNode pHead){
if(pHead == null){
return null;
}
//
cloneNodes(pHead);
//
connectSibling(pHead);
//
return reconnectNodes(pHead);
}
//
public void cloneNodes(RandomListNode head){
RandomListNode nowNode = head;
while(nowNode != null){
RandomListNode clonedNode = new RandomListNode(nowNode.label);
clonedNode.next = nowNode.next;
nowNode.next = clonedNode;
nowNode = clonedNode.next;
}
}
//
public void connectSibling(RandomListNode head){
RandomListNode nowNode = head;
while(nowNode != null){
RandomListNode cloned = nowNode.next;
if(nowNode.random != null){
cloned.random = nowNode.random.next;
}
nowNode = cloned.next;
}
}
//
public RandomListNode reconnectNodes(RandomListNode head){
RandomListNode clonedHead = head.next;
RandomListNode nowNode = head;
while(nowNode != null){
RandomListNode clonedNode = nowNode.next;
nowNode.next = clonedNode.next;
clonedNode.next = clonedNode.next == null ? null : clonedNode.next.next;
nowNode = nowNode.next;
}
return clonedHead;
}
public static void main(String[] args) {
RandomListNode head = new RandomListNode(1);
RandomListNode node1 = new RandomListNode(2);
RandomListNode node2 = new RandomListNode(3);
head.next = node1;
node1.next = node2;
head.random = node2;
node1.random = node2;
node2.random = head;
CopyList test = new CopyList();
RandomListNode cloneHead = test.Clone(head);
while(cloneHead != null){
if(cloneHead.random != null){
System.out.println(cloneHead.random.label);
}else{
System.out.println("-");
}
cloneHead = cloneHead.next;
}
}
}
class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}