输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

我的解法：

1. 复制一份链表，不考虑random指针
2. 设置复制链中节点的random指针

public class Solution {
    public RandomListNode Clone(RandomListNode pHead){
        if(pHead == null) return null;
        RandomListNode pHead2 = copyNode(pHead);
        
        RandomListNode index2 = pHead2;
        RandomListNode index = pHead;
        while(index != null){
            index2.random = findNode(index.random,pHead2);
            index2 = index2.next;
            index = index.next;
        }
        return pHead2;
    }
    // 复制直链表
    public RandomListNode copyNode(RandomListNode pHead){
        RandomListNode pHead2 = new RandomListNode(pHead.label);
        
        RandomListNode index2 = pHead2;
        pHead = pHead.next;

        while(pHead != null){
            index2.next = new RandomListNode(pHead.label);
            index2 = index2.next;
            pHead = pHead.next;
        }
        return pHead2;
    }
   //设置random指针
    public RandomListNode findNode(RandomListNode find,RandomListNode head){
        if(find == null) return null;
        while(head!=null){
            if(head.label == find.label){
                return head;
            }else head = head.next;
        }
        return null;
    }
}

改进解法

我的解法要为每一个节点findNode，所以复杂度为n2。结合链表高效的插入和删除操作，有如下改进

1. 不考虑random指针复制，新的节点放在原节点后面
2. 设置每个节点的random指针
3. 分离出被复制的节点

因为没有循环的嵌套，复杂降为n

image.png

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead){
        if(pHead == null ) return null;
        copyNode(pHead);
        setRandomPointer(pHead);
        return splitLink(pHead);
    }
    public void copyNode(RandomListNode pHead){
        while(pHead != null){
            RandomListNode node = new RandomListNode(pHead.label);
            node.next = pHead.next;
            pHead.next = node;
            pHead = node.next;;
        }
    }
    public void setRandomPointer(RandomListNode pHead){
        for(;pHead != null;pHead = pHead.next.next){
            // 注意判断random指针是否为空
            if(pHead.random != null) 
                // 复制节点的random指针 = 被复制节点的random的next
                pHead.next.random = pHead.random.next;
        }
    }
    public RandomListNode splitLink(RandomListNode pHead){
        RandomListNode pHead2 = pHead.next;
        RandomListNode index = pHead2;
        // 循环判断条件
        for(;index.next != null;index = index.next){
            index.next = index.next.next;
        }
        pHead.next = null;//输出结果中请不要返回参数中的节点引用
        return pHead2;
    }
}