138. Copy List with Random Point

题目分析

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.
思路参考
思路参考

代码

import java.util.*;
/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        Map<RandomListNode, RandomListNode> hm = new HashMap<>();
        RandomListNode headCopy = new RandomListNode(head.label);
        hm.put(head, headCopy);
        RandomListNode p1 = head;
        RandomListNode p2 = headCopy;
        while(p1!= null) {
            if(p1.next != null) {
                if(hm.containsKey(p1.next)) {  // 这个结点已经创建过了
                    p2.next = hm.get(p1.next);
                } else {  // 创建新结点，并加入 map 中
                    RandomListNode nextTemp = new RandomListNode(p1.next.label);
                    p2.next = nextTemp;
                    hm.put(p1.next, p2.next);
                }
            } else {
                p2.next = null;
            }
            if(p1.random != null) {
                if(hm.containsKey(p1.random)) {  // 这个结点已经创建过了
                    p2.random = hm.get(p1.random);
                } else {
                    RandomListNode randomTemp = new RandomListNode(p1.random.label);
                    p2.random = randomTemp;
                    hm.put(p1.random, p2.random);
                }
            } else {
                p2.random = null;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return headCopy;
    }
}