题目：

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

第一种方法

思路：

• （1）将链表中的节点用列表存储
• （2）然后遍历查找每个节点中random指向列表中的哪一个节点对象，并按照列表顺序存储节点random指向的节点对象的下标。
• （3）创建新节点列表
• （4）将新节点中的next和random进行链接。

1587908166698.png

代码：

import java.util.ArrayList;

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

        RandomListNode(int label) {
            this.label = label;
        }
    }
    public ArrayList<RandomListNode> toArray(RandomListNode pHead){
        if(pHead==null){
            return null;
        }
        ArrayList<RandomListNode> result=new ArrayList<RandomListNode>();
        RandomListNode key=pHead;
        while(key!=null){
            result.add(key);
            key=key.next;
        }
        return result;
    }
    public int getRandomIndex(ArrayList<RandomListNode> oldNode,RandomListNode key){
        for(int i=0;i<oldNode.size();i++){
            if(oldNode.get(i).equals(key)){
                return i;
            }
        }
        return -1;
    }
    public int[] getRandomList(ArrayList<RandomListNode> oldNode){
        int [] result=new int[oldNode.size()];
        for(int i=0;i<oldNode.size();i++){
            result[i]=this.getRandomIndex(oldNode,oldNode.get(i).random);
            System.out.println(result[i]);
        }
        return result;
    }
    public RandomListNode copyNode(RandomListNode old){
        return new RandomListNode(old.label);
    }
    public ArrayList<RandomListNode> getNewList(ArrayList<RandomListNode> oldNode){
        ArrayList<RandomListNode> newNode=new ArrayList<>();
        for(int i=0;i<oldNode.size();i++){
            newNode.add(this.copyNode(oldNode.get(i)));
        }
        return newNode;
    }
    public RandomListNode getNewLink(ArrayList<RandomListNode> newNode,int [] randomList){

        RandomListNode root=newNode.get(0);
        RandomListNode key=root;
        for(int i=1;i<newNode.size();i++){
            key.next=newNode.get(i);
            key=key.next;
        }
        for(int i=0;i<randomList.length;i++){
            if(randomList[i]!=-1){
                newNode.get(i).random=newNode.get(randomList[i]);
            }
        }
        return root;
    }
    public RandomListNode Clone(RandomListNode pHead)
    {
        //第1步：将原始链表数组化 时间复杂度（n）,空间复杂度（n）
        ArrayList<RandomListNode> oldNode=this.toArray(pHead);
        if(oldNode==null){
            return null;
        }
        //第2步：遍历查询random所指向的node 时间复杂度（n^2）,空间复杂度（0）
        int [] randomList=this.getRandomList(oldNode);
        //第3步：根据数组重新创建一个新Node数组，next和random都为null 时间复杂度（n）,空间复杂度（n）
        ArrayList<RandomListNode> newNode=this.getNewList(oldNode);
        //第4步:链接链表 时间复杂度（n）,空间复杂度（0）
        RandomListNode newRoot=this.getNewLink(newNode,randomList);
        return newRoot;
    }
    public RandomListNode create(){
        RandomListNode r1=new RandomListNode(1);
        RandomListNode r2=new RandomListNode(2);
        RandomListNode r3=new RandomListNode(3);
        RandomListNode r4=new RandomListNode(4);
        RandomListNode r5=new RandomListNode(5);
        RandomListNode r6=new RandomListNode(6);
        RandomListNode r7=new RandomListNode(7);
        RandomListNode r8=new RandomListNode(8);
        r1.next=r2;
        r2.next=r3;
        r3.next=r4;
        r4.next=r5;
        r5.next=r6;
        r6.next=r7;
        r7.next=r8;
        r1.random=r3;
        r2.random=r4;
        r3.random=r5;
        r4.random=r6;
        r5.random=r7;
        r6.random=r8;
        r7.random=r1;
        r8.random=r2;
        return r1;
    }

    public static void main(String[] args) {
        Solution1 s=new Solution1();
        RandomListNode root=s.create();
        s.Clone(root);
    }
}

算法分析：

该方法最复杂的地方就是寻找random所指向的节点。

时间复杂度O(n^2),空间复杂度O(n)

代码运行：

运行时间：24ms

占用内存：9656k

第二种方法

这个题目最大的难点在于random引用如何便捷正确的指向对应的新节点。

本方法思路：

• （1）依次创建新的节点插入到对应的旧节点之后

• （2）此时新节点的random就在旧节点的random后面，根据这一规律，对新节点的random进行赋值。

• （3）将组合链表中旧节点删除，可以借助一个额外节点作为暂时的根节点。

  1587969275319.png

代码：

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

        RandomListNode(int label) {
            this.label = label;
        }
    }
    public void insertNewNodeInLink(RandomListNode pHead){
        RandomListNode p=pHead;
        while(p!=null){
            RandomListNode q=new RandomListNode(p.label);
            q.next=p.next;
            p.next=q;
            p=q.next;
        }
    }
    public void replaceRandom(RandomListNode pHead){
        RandomListNode t=pHead;
        while(t!=null){
            RandomListNode q=t.next;
            if(t.random!=null)
                q.random=t.random.next;
            t=q.next;

        }
    }
    public RandomListNode getNewLink(RandomListNode pHead){
        RandomListNode s=new RandomListNode(0);
        RandomListNode s1=s;
        while(pHead!=null){
            RandomListNode  q=pHead.next;
            pHead.next=q.next;
            q.next=s.next;
            s.next=q;
            s=s.next;
            pHead=pHead.next;


        }
        return s1.next;
    }
    public RandomListNode Clone(RandomListNode pHead)
    {
        //第一步：遍历创建新的复制节点，并将其插入到旧链表中被复制节点之后 时间复杂度（n）,空间复杂度（0）
        this.insertNewNodeInLink(pHead);
        //第二步：因为新节点就在旧节点的后一个节点，因此random所指的旧节点向下移一个，就能够指向新节点 时间复杂度（n）,空间复杂度（0）
        this.replaceRandom(pHead);
        //第三步：将新节点串联成新的链表 时间复杂度（n）,空间复杂度（0）
        RandomListNode newroot = this.getNewLink(pHead);

        return newroot;

    }
    public RandomListNode create(){
        RandomListNode r1=new RandomListNode(1);
        RandomListNode r2=new RandomListNode(2);
        RandomListNode r3=new RandomListNode(3);
        RandomListNode r4=new RandomListNode(4);
        RandomListNode r5=new RandomListNode(5);
        RandomListNode r6=new RandomListNode(6);
        RandomListNode r7=new RandomListNode(7);
        RandomListNode r8=new RandomListNode(8);
        r1.next=r2;
        r2.next=r3;
        r3.next=r4;
        r4.next=r5;
        r5.next=r6;
        r6.next=r7;
        r7.next=r8;
        r1.random=r3;
        r2.random=r4;
        r3.random=r5;
        r4.random=r6;
        r5.random=r7;
        r6.random=r8;
        r7.random=r1;
        r8.random=r2;
        return r1;

    }

    public static void main(String[] args) {
        Solution2 s=new Solution2();
        RandomListNode root=s.create();
        RandomListNode t=s.Clone(root);

        while(t!=null){
            System.out.println(t.label);
            t=t.next;
        }
    }
}

算法分析

空间复杂度：O(0)

时间复杂度：O(n)

运行代码：

运行时间：19ms

占用内存：9428k