题解 | #复杂链表的复制#

import java.util.*;
/*
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;
        }
        //建立三个集合，分别按顺序保存原始节点，原始节点对应的random节点，按序新建的clone节点
        ArrayList<RandomListNode> originList = new ArrayList<>();
        ArrayList<RandomListNode> originRandomList = new ArrayList<>();
        ArrayList<RandomListNode> cloneList = new ArrayList<>();

        while (pHead != null) {
            RandomListNode clone = new RandomListNode(pHead.label);

            //第一次遍历，把节点分别添加到三个集合    
            originList.add(pHead);
            originRandomList.add(pHead.random);
            cloneList.add(clone);

            pHead = pHead.next;
        }


        //第二次遍历，建立原始节点和random节点的坐标index的映射关系，以便clone节点直接通过ArrayList角标指向目标
        for (int i = 0; i < originList.size(); i++) {
            if (originRandomList.get(i) != null) {
                int index = originList.indexOf(originRandomList.get(i));
                cloneList.get(i).random = cloneList.get(index);
            } else {
                cloneList.get(i).random = null;
            }

            //顺便把clone的链表每个节点连接起来
            if (i < originList.size() - 1) {
                cloneList.get(i).next = cloneList.get(i + 1);
            } else {
                cloneList.get(i).next = null;
            }
        }

        //最后返回结果
        return cloneList.get(0);
    }
}