复杂链表的复制

复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。

Paste_Image.png

代码如下：

public class ComplexListCopy {
    

    
    public static RandomListNode clone(RandomListNode pHead){
        if(pHead == null){
            throw new NullPointerException();
        }
        
        RandomListNode pCur = pHead;
        RandomListNode pNext = pCur.next;
        
        //复制
        while(pNext != null){
            pCur.next = new RandomListNode(pCur.label);
            pCur.next.next = pNext;
            pCur = pNext;
            pNext = pNext.next;
        }
        //如果pNext==null，把pCurr.next指向他的复制品
        pCur.next = new RandomListNode(pCur.label);
        
        //构造random
        pCur = pHead;
        while(pCur != null){
            if(pCur.random != null){
                pCur.next.random = pCur.random.next;
            }
            pCur = pCur.next.next;
        }
        
        //拆分链表
        pCur = pHead;
        RandomListNode cHead = pCur.next;
        pNext = pCur.next.next;
        RandomListNode cTem = cHead;
        while(pNext != null){
            //当前的下一个指向pNext
            pCur.next = pNext;
            //复制品的下一个指向pNext.next(pNext存在，必然pNext.next存在（是pNext的复制品）)
            cTem.next = pNext.next;
            //把cTem指向cTem.next
            cTem = cTem.next;
            //pCur指向pNext
            pCur = pNext;
            //pNext指向pNext.next.next（一个next是他的复制，再next才是实际上的next）
            pNext = pNext.next.next;
        }
        //不要漏掉这个，不然原链表最后会出现一个复制品
        pCur.next = null;
        
        return cHead;
        
    }

    //测试数据
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        RandomListNode root = new RandomListNode(1);
        RandomListNode root2 = new RandomListNode(2);
        RandomListNode root3 = new RandomListNode(3);
        RandomListNode root4 = new RandomListNode(4);
        RandomListNode root5 = new RandomListNode(5);
        RandomListNode root6 = new RandomListNode(6);
        
        root.next = root2;
        root2.next = root3;
        root3.next = root4;
        root4.next = root5;
        root5.next = root6;
        
        root4.random = root6;
        root.random = root6;
        root3.random = root;
                
        print(root);
        RandomListNode clone = clone(root);
        print(clone);
        
        
    }
    
    public static void print(RandomListNode node){
        RandomListNode tem = node;
        while(tem != null){
            System.out.print(tem.label + " " );
            if(tem.random != null){
                System.out.print(tem.random.label + " ");
            }
            tem = tem.next;
        }
        System.out.println("");

    }

}

class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

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