You are given a list of length N, and each node contains an additional random pointer, random, which can point to any node or empty node in the list.

Construct a deep copy of the list. The deep copy should consist of exactly N new nodes, with each new node set to the value of its corresponding 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 a replicated list should point to a node in the original list.

For example, if there are two nodes X and Y in the original linked list, where x. randdom –> Y. Then the corresponding two nodes x and y in the replication list also have x. randdom –> y.

Returns the head node of the replication list.

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

Val: an integer representing Node.val. Random_index: the 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 accepts only the head of the original list as an argument.

 

  • Example 1:

Input: the head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] output: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]

  • Example 2:

Input: head = [1,1],[2,1]] output: [[1,1],[2,1]]

  • Example 3:

Input: the head = [[3, null], [3, 0], [3, null]] output: [[3, null], [3, 0], [3, null]]

Their thinking

  1. First copy a new node according to the value of the original node and attach it to the original node to form the original node 1-> new node 1-> original node 2-> new node 2… Linked lists like this.
  2. Then assign a value to the random pointer of the new node. According to the node pointed to by the random pointer of the original node, the last bit of the node is the corresponding new node. Therefore, we only need to point the pointer to this node.
  3. The original and new nodes are then separated to form two linked lists and the new linked list is returned

code

/* // 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) {

        if (head == null)
            return null;
        Node h = head;
        while(h ! =null) {
            Node node = new Node(h.val);
            Node next = h.next;
            h.next = node;
            node.next = next;
            h = next;
        }
        h = head;
        while(h ! =null) {
            Node next = h.next;
            if(h.random ! =null)
                next.random = h.random.next;
            h = h.next.next;
        }
        Node s = head.next, res = s, pre = head;

        while(s.next ! =null) {
            pre.next = s.next;
            s.next = s.next.next;
            pre = pre.next;
            s = s.next;
        }
        pre.next = null;
        returnres; }}Copy the code