138. Copy List with Random Pointer.md

138. Copy List with Random Pointer

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.

Solution

用递归，或者迭代遍历两遍（用dict找到copy前后的node的对应关系。

COde

# 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 copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if head is None:
            return 
        headcopy = RandomListNode(head.label)
        pre_nodecopy = headcopy
        dic = {head:headcopy}
        node = head.next
        while node:
            cur_nodecopy = RandomListNode(node.label)
            dic[node] = cur_nodecopy
            pre_nodecopy.next = cur_nodecopy
            pre_nodecopy = cur_nodecopy
            node = node.next
        
        node = head
        while node:
            random_node = node.random
            if random_node:
                dic[node].random = dic[random_node]
            node = node.next
        return headcopy
            

Code - 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 {
    Map<Node, Node> map = new HashMap<Node,Node>();
    public Node copyRandomList(Node head) {
        if(head == null)
            return head;
        if(map.get(head)==null)
        {
            Node node = new Node(head.val,null,null);
            map.put(head, node);
            node.random = copyRandomList(head.random);
            node.next = copyRandomList(head.next);
        }
        return map.get(head);
    }
}

Code-递归

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random
"""
class Solution(object):
    def __init__(self):
        self.record = {}
        
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if head is None:
            return None
        if head not in self.record:
            new_node = Node(head.val, None, None)
            self.record[head] = new_node
            new_node.next = self.copyRandomList(head.next)
            new_node.random = self.copyRandomList(head.random)  
        return self.record[head]