Leetcode 138 Copy List with Random Pointer

Description

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.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val

random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Solution

1. Deep copy 不能简单遍历原linkedlist, 对next和random所指向的node进行new Node(node.val)操作，要考虑不同地址的node有可能具有相同的val值
2. 使用HashMap，遍历原LinkedList, 列表中每一个结点做为key以当前遍历结点的val值创建与之对应的新结点并存为value
3. 重新遍历原LinkedList,并从Map中取出简直对来进行next和random指针对赋值操作

    class Solution {
        public Node copyRandomList(Node head) {
            if(head == null)
                return null;

            Map<Node, Node> map = new HashMap<>();
            Node cur = head;
            while(cur != null){
                map.put(cur, new Node(cur.val));
                cur = cur.next;
            }

            Node dummyHead = new Node(-1);
            Node curCopy = dummyHead;
            cur = head;
            while(cur != null){
                curCopy.next = map.get(cur);
                curCopy.next.random = map.get(cur.random);
                cur = cur.next;
                curCopy = curCopy.next;
            }

            return dummyHead.next;
        }
    }