题目：请实现函数ComplexListNode clone(ComplexListNode head),复制一个复杂链表。在复杂链表中，每个结点除了有一个next 域指向下一个结点外，还有一个sibling 指向链表中的任意结点或者null。
代码如下：
package demo;
public class Test26 {
public static class ComplexListNode {
int value;
ComplexListNode next;
ComplexListNode sibling;
}
public static ComplexListNode clone(ComplexListNode head) {
// 如果链表为空，就直接返回空
if (head == null) {
return null;
}
// 先复制结点
cloneNodes(head);
// 再链接sibling字段
connectNodes(head);
// 最后将整个链表拆分，返回复制链表的头结点
return reconnectNodes(head);
}
/**
* 复制一个链表，并且将复制后的结点插入到被复制的结点后面， 只链接复制结点的next字段
*
* @param head
*/
private static void cloneNodes(ComplexListNode head) {
// 如果链表非空，进行复制操作
while (head != null) {
// 创建一个复制结点
ComplexListNode tmp = new ComplexListNode();
// 将被复制的结点的值传给复制结点
tmp.value = head.value;
// 复制结点的next指向下一个要被复制的结点
tmp.next = head.next;
// 被复制的结点的next指向新结点
head.next = tmp;
// head指向下一个被复制结点的位置
head = tmp.next;
}
}
/**
* 设置复制结点的sibling字段
*
* @param head
*/
private static void connectNodes(ComplexListNode head) {
// 如果链表不为空
while (head != null) {
// 如果当前结点的sibling字段不为空，则需要设置复制结点的sibling字段
if (head.sibling != null) {
// 当前结点的sibling指向的结点的下一个结点，就是当前结点的复制结点的sibling指向的结点
head.next.sibling = head.sibling.next;
}
// 指向下一个要处理的结点
head = head.next.next;
}
}
/**
* 将当前结点和复制结点拆分成2个链表
*
* @param head
* 链表的头结点
* @return 复制链表的头结点
*/
private static ComplexListNode reconnectNodes(ComplexListNode head) {
// 如果链表为空，直接返回空
if (head == null) {
return null;
}
// 记录复制链表的头结点
ComplexListNode newHead = head.next;
// 记录当前处理的复制结点
ComplexListNode pointer = newHead;
// 被复制结点的next指向下一个被复制结点
head.next = newHead.next;
// 指向新的被复制结点
head = head.next;
while (head != null) {
pointer.next = head.next;
pointer = pointer.next;
head.next = pointer.next;
head = head.next;
}
return newHead;
}
/**
* 打印单链表
*
* @param head
*/
public static void printList(ComplexListNode head) {
while (head != null) {
System.out.print(head.value + "->");
head = head.next;
}
System.out.println("null");
}
/**
* 判断2个链表是否是同一个链表
*
* @param head1
* @param head2
* @return
*/
public static boolean isSameList(ComplexListNode head1, ComplexListNode head2) {
while (head1 != null && head2 != null) {
if (head1 == head2) {
head1 = head1.next;
head2 = head2.next;
} else {
return false;
}
}
return head1 == null && head2 == null;
}
}
