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

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;
        }
        ArrayList<RandomListNode> arrayListRandom = new ArrayList<>();
        ArrayList<RandomListNode> list = new ArrayList<>();
        ArrayList<RandomListNode> arrayListClone = new ArrayList<>();

        RandomListNode temp = new RandomListNode(pHead.label);
        RandomListNode newHead = temp;

        while (pHead.next != null) {
            if (pHead.next == null) {
                temp.next = null;
            } else {
                temp.next = new RandomListNode(pHead.next.label);
            }

            arrayListRandom.add(pHead.random);//理清楚random的关系
            list.add(pHead);

            arrayListClone.add(temp);

            //遍历完成，还需要把原集合的random指向关系也取出来保存好

            //这样，新的链表，才知道random该指向哪个节点，如果random指向是new出来的，那一定错了

            //向前遍历
            temp = temp.next;
            pHead = pHead.next;
        };

        arrayListRandom.add(pHead.random);
        list.add(pHead);
        arrayListClone.add(temp);


        System.out.println("arrayListRandom.size():" + (arrayListRandom.size()));
        System.out.println("arrayListClone.size():" + (arrayListClone.size()) +
                           (arrayListClone.get(0).label) + "," + (arrayListClone.get(
                                       arrayListClone.size() - 1).label));
        System.out.println("list.size():" + (list.size()));
        //所有的点都在集合中了，这个时候每拿出来一个，就新建一个对象
        for (int i = 0; i < arrayListRandom.size(); i++) {
            RandomListNode random = arrayListRandom.get(i);
            if (random != null) {
                //这一步，主要是为了建立节点和random的映射关系；
                int randomIndex = list.indexOf(random);/** 非常关键的一步，建立映射关系 */
                arrayListClone.get(i).random = arrayListClone.get(randomIndex);
            } else {
                arrayListClone.get(i).random = null;
            }
        }

        return newHead;
    }
}