题目：请实现一个函数，复制一个复杂链表。
在复杂链表中，每个结点除了有一个next指针指向下一个结点外，还有一个sibling指针指向链表中的任意结点或者nulL
直观解法：
1.遍历链表，复制链表节点，并连接next节点。2.遍历链表，连接sibling节点。对于一个有n个节点的链表，由于定位每个节点的silbing节点都需要从链表的头结点开始经过O(n)步才能实现，因此这种方法的时间复杂度是O(n2)
优化解法：上述方法的时间主要是用在了sibling节点的定位上，考虑优化此步骤。具体的做法是在复制节点的时候，把原节点N和复制出来的N'节点用一个map保存起来，这样在第二部连接sibling结点的时候就可以以O(1)的时间复杂度定位到相应的sibling节点，总体时间复杂度为O(n)，空间复杂度也是O(n)
最优算法：
第一步：根据原始链表的每个节点创建对应的复制结点，把复制结点连接在原结点的后面
第二步：设置复制出来的结点的任意结点sibling节点
第三步：把长链表拆分成两个链表
package Solution;
public class No26CopyComplexList {
static class ComplexListNode{
int value;
ComplexListNode next;
ComplexListNode sibling;
public ComplexListNode(){
}
public ComplexListNode(int value,ComplexListNode next,ComplexListNode sibling){
this.value=value;
this.next=next;
this.sibling=sibling;
}
}
//把复杂链表中的所有结点进行复制，并连接在原结点的后面
private static void cloneNode(ComplexListNode head){
ComplexListNode node=head;
while(node!=null){
ComplexListNode clonedNode=new ComplexListNode();
clonedNode.value=node.value;
clonedNode.next=node.next;
clonedNode.sibling=null;
node.next=clonedNode;
node=clonedNode.next;
}
}
//设置复制的节点的指向任意结点的连接关系
private static void connectSiblingNodes(ComplexListNode head){
ComplexListNode node=head;
while(node!=null){
ComplexListNode clonedNode=node.next;
if(node.sibling!=null){
clonedNode.sibling=node.sibling.next;
}
node=clonedNode.next;
}
}
//把长链表拆分成两个单独的链表，并返回复制后的链表的头结点
private static ComplexListNode reconnectNodes(ComplexListNode head){
ComplexListNode node=head;
ComplexListNode clonedHead=null;
ComplexListNode clonedNode=null;
if(node!=null){
clonedHead=clonedNode=node.next;
node.next=clonedNode.next;
node=clonedNode.next;
}
while(node!=null){
clonedNode.next=node.next;
clonedNode=node.next;
node.next=clonedNode.next;
node=clonedNode.next;
}
return clonedHead;
}
public static ComplexListNode copyComplexList(ComplexListNode head){
if(head==null)
return null;
cloneNode(head);
connectSiblingNodes(head);
return reconnectNodes(head);
}
public static void printComplexList(ComplexListNode head){
ComplexListNode node=head;
int value=0;
ComplexListNode next=null;
ComplexListNode sibling=null;
while(node!=null){
value=node.value;
next=node.next;
sibling=node.sibling;
StringBuilder sb=new StringBuilder("当前节点的值为：").append(value);
if(next!=null)
sb.append(",下一结点的值为：").append(next.value);
else
sb.append(",当前结点为尾节点");
if(sibling!=null)
sb.append(",指向任意结点的值为：").append(sibling.value);
else
sb.append(",没有指向其他结点的任意结点");
System.out.println(sb.toString());
node=node.next;
}
}
public static void main(String[] args) {
ComplexListNode node1=new ComplexListNode();
ComplexListNode node2=new ComplexListNode();
ComplexListNode node3=new ComplexListNode();
ComplexListNode node4=new ComplexListNode();
ComplexListNode node5=new ComplexListNode();
node1.value=1;
node1.next=node2;
node1.sibling=node3;
node2.value=2;
node2.next=node3;
node2.sibling=node5;
node3.value=3;
node3.next=node4;
node3.sibling=null;
node4.value=4;
node4.next=node5;
node4.sibling=node2;
node5.value=5;
node5.next=null;
node5.sibling=null;
printComplexList(node1);
System.out.println("=========================开始复制============================");
printComplexList(copyComplexList(node1));
}
}