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

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) {
	  //存储所有新的节点，方便后期找到random节点
        Map<Integer, RandomListNode> map = new HashMap<>();
        RandomListNode cur = pHead;
        RandomListNode dummyHead = new RandomListNode(-1);
        RandomListNode newHead = dummyHead;
		//一个循环搞定前后关系
        while (cur != null) {
            RandomListNode newNode = new RandomListNode(cur.label);
            map.put(cur.label, newNode);
            newHead.next = newNode;
            newHead = newNode;
            cur = cur.next;
        }
		//一个循环搞定random
        cur = pHead;
        newHead = dummyHead.next;
        while (cur != null) {
            RandomListNode random = cur.random;
            RandomListNode newRandom = null;
            if (random != null) {
                newRandom = map.get(cur.random.label);
            }
            newHead.random = newRandom;
            newHead = newHead.next;
            cur = cur.next;
        }

        return dummyHead.next;
    }
}