2021-07-22 LeetCode Daily question

Link: leetcode-cn.com/problems/co…

Tags: hash table, linked list

The title

Given a list of length n, each node contains an additional pointer random, which can point to any node or null node in the list.

Construct a deep copy of the list. The deep copy should consist of exactly n new nodes, each of which has the same value as the original node. The next and random Pointers of the new node should also point to the new node in the replicated list, so that these Pointers in the original and replicated lists represent the same list state. No pointer in the copied list should point to a node in the original list.

For example, if the original list has two nodes X and Y, where x. randam –> Y. Then the corresponding two nodes x and y in the replicated list also have x. randam –> y.

Returns the head node of the replicated list.

The linked list in the input/output is represented by a list of n nodes. Each node is represented by a [val, random_index] :

  • Val: an integer representing node. val.
  • Random_index: Index of the node to which the random pointer points (range 0 to n-1); Null if it does not point to any node.

Your code only accepts the head node of the original list as an argument.

Example 1:

Type: head = [[7.null], [13.0], [11.4], [10.2], [1.0[] output: [[7.null], [13.0], [11.4], [10.2], [1.0]]
Copy the code

Example 2:

Type: head = [[1.1], [2.1[] output: [[1.1], [2.1]]
Copy the code

Example 3:

Type: head = [[3.null], [3.0], [3.null[] output: [[3.null], [3.0], [3.null]]
Copy the code

Example 4:

Input: head = [] Output: [] Explanation: The given list is null (null pointer), so returnnull.Copy the code

Tip:

  • 0 <= n <= 1000
  • -10000 <= Node.val <= 10000
  • Node.random is null or points to a Node in the list.

Analysis of the

First understand what a deep copy is. Deep copy means that the address of the object to be copied is different from that of the original object. Changing the object to be copied does not affect the value of the original object. The shallow copy is to change the value of the copied object, and the value of the original object will also change.

So you can’t just iterate over the assignment, otherwise you’re still pointing to the address of the original object. If we don’t have a random pointer here, we can do it, we can iterate, and we can create a new node. But with this random pointer, you can’t just say new, so you don’t know what node it points to.

My idea is to ignore the random pointer, first all new nodes new, and later to add random, see the code for details.

coding

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; }} * /

class Solution {
    public Node copyRandomList(Node head) {
        Node res = null;
        List<Node> list = new ArrayList<>();

        while(head ! =null) {
            list.add(head);
            head = head.next;
        }

        if (list.size() == 0) {
            return res;
        }

        res = new Node(list.get(0).val);
        Node temp = res;
        // The key is the old node and the new node of the value, so that the new node can be found through the old node
        Map<Node, Node> copy = new HashMap<>();
        copy.put(list.get(0), res);

        for (int i = 1; i < list.size(); i++) {
            Node node = new Node(list.get(i).val);
            temp.next = node;
            copy.put(list.get(i), node);
            
            temp = temp.next;
        }

        for (int i = 0; i < list.size(); i++) {
            Node node = list.get(i);
            copy.get(node).random = copy.get(node.random);
        }

        returnres; }}Copy the code