復(fù)雜鏈表的復(fù)制

輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為復(fù)制后復(fù)雜鏈表的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;
        
        //復(fù)制
        while(pNext != null){
            pCur.next = new RandomListNode(pCur.label);
            pCur.next.next = pNext;
            pCur = pNext;
            pNext = pNext.next;
        }
        //如果pNext==null，把pCurr.next指向他的復(fù)制品
        pCur.next = new RandomListNode(pCur.label);
        
        //構(gòu)造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){
            //當(dāng)前的下一個(gè)指向pNext
            pCur.next = pNext;
            //復(fù)制品的下一個(gè)指向pNext.next(pNext存在，必然pNext.next存在（是pNext的復(fù)制品）)
            cTem.next = pNext.next;
            //把cTem指向cTem.next
            cTem = cTem.next;
            //pCur指向pNext
            pCur = pNext;
            //pNext指向pNext.next.next（一個(gè)next是他的復(fù)制，再next才是實(shí)際上的next）
            pNext = pNext.next.next;
        }
        //不要漏掉這個(gè)，不然原鏈表最后會(huì)出現(xiàn)一個(gè)復(fù)制品
        pCur.next = null;
        
        return cHead;
        
    }

    //測(cè)試數(shù)據(jù)
    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;
    }
}