138. Copy List with Random Pointer (Medium)

https://leetcode.com/problems/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.

 

Example 1:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

 

Note:

  1. You must return the copy of the given head as a reference to the cloned list.

Solutions

class Solution {

    // The description of this problem is vague and the first response for it is simple, but why
    // tagged as medium difficulty?

    // I think the most most difficult part is the circles formed by the random link. We need to keep
    // track of the visited nodes to avoid deadlock. Also, there may be some independent nodes that
    // not linked by next, but linked by random pointer.

    public Node copyRandomList(Node head) {
        Map<Node, Node> nodeMap = new HashMap<>();

        return recurse(head, nodeMap);
    }

    public Node recurse(Node head, Map<Node, Node> visited) {
        if (head == null) {
            return null;
        }

        if (visited.containsKey(head)) {
            return visited.get(head);
        }

        Node copy = new Node(head.val, null, null);

        visited.put(head, copy);

        copy.next = recurse(head.next, visited);
        copy.random = recurse(head.random, visited);

        return copy;
    }
}

Incorrect Solutions

class Solution {

    // Incorrect solution.

    // The description of this problem is vague and the first response for it is simple, but why
    // tagged as medium difficulty?

    // I think the most most difficult part is the circles formed by the random link. We need to keep
    // track of the visited nodes to avoid deadlock. Also, there may be some independent nodes that
    // not linked by next, but linked by random pointer.

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

        Set<Node> visited = new HashSet<>();

        Node copy = new Node(-1, null, null);

        recurse(head, copy, visited);

        return copy;
    }

    public void recurse(Node head, Node copy, Set<Node> visited) {

        // In practice, following null check is not necessary.
        if (head == null) {
            return;
        }

        if (visited.contains(head)) {
            return;
        }

        visited.add(head);

        copy.val = head.val;

        if (head.next != null) {
            copy.next = new Node(-1, null, null);

            recurse(head.next, copy.next, visited);
        }

        if (head.random != null) {
            copy.random = new Node(-1, null, null);

            recurse(head.random, copy.random, visited);
        }
    }
}

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-20 20:50:22

results matching ""

    No results matching ""