138 Copy List with Random Pointer

使用哈希表进行存储

# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def __init__(self):
        # hash : using the visited nodes as key and the new keys as value
        self.hash = {}
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if head is None:
            return None
        if head in self.hash:
            return self.hash[head]
        node = RandomListNode(head.label)
        self.hash[head] = node
        node.next = self.copyRandomList(head.next)
        node.random = self.copyRandomList(head.random)
        return node

Java

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        Map<Node, Node> map = new HashMap();
        Node node = head;
        // the first loop copy only the value of the nodes
        while(node != null){
            map.put(node, new Node(node.val));
            node = node.next;
        }
        node = head;
        // the second copy: copy the next and the random pointers
        while(node != null){
            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);
            node = node.next;
        }
        return map.get(head);
    }
}

知识点

• Java Map的基本操作:

  • 定义: Map<Node, Node> map = new HashMap();

  • get(key),put(key, value)