字典存储随机节点法

• 第一次循环复制新链，并且建立新节点和旧节点的映射存入map中
• 第二次循环利用map给新链重定向随机节点指向

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

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        Map<RandomListNode, RandomListNode> map = new HashMap();
        RandomListNode head = new RandomListNode(-1), node = head, pre;
        // 克隆链表
        while(pHead != null) {
            pre = node;
            // 深拷贝节点
            node = new RandomListNode(pHead.label);
            node.random = pHead.random;
            // 连接
            pre.next = node;
            // 存入映射
            map.put(pHead, node);
            pHead = pHead.next;
        }
        // 克隆随机节点
        node = head.next;
        while(node != null) {
            node.random = map.get(node.random);
            node = node.next;
        }
        return head.next;

    }
}

后置节点法

• 第一个循环创建复制节点，并放置原节点之后
• 第二个循环给每一个复制节点的随机指针赋值
• 第三个循环独立出复制节点，并还原链

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

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        Map<RandomListNode, RandomListNode> map = new HashMap();
        RandomListNode head = new RandomListNode(-1), node = head, pre;
        head.next = pHead;
        // 将克隆节点放到原节点后
        while(pHead != null) {
            node = new RandomListNode(pHead.label);
            node.random = pHead.random;
            node.next = pHead.next;
            pHead.next = node;
            pHead = node.next;
        }

        // 给克隆节点的随机节点赋值
        node = head.next;
        while(node != null) {
            node = node.next;
            node.random = node.random == null ? null : node.random.next;
            node = node.next;
        }

        // 独立出克隆节点
        node = head;
        pHead = head.next;
        while(node.next != null) {
            pre = node;
            node = node.next.next;
            pHead.next = node.next;
            pre.next = node;
            pHead = pHead.next;
        }
        return head.next;
    }
}