Subject to introduce

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: a representationNode.valThe integer.
• random_index: Index of the node to which the random pointer points (ranges from0 到 n-1); If it does not point to any nodenull 。

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

Example 1

Enter: 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

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

Example 3

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

Example 4

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

Tip:

• 0 <= n <= 1000
• -10000 <= Node.val <= 10000
• Node.randomIs null or points to a node in the linked list.

Leetcode-138 copy list with random pointer sword refers to the copy b site video of the offer-35 complex list

Their thinking

1. Copy each node in the linked list and insert the copied node between the current node and the next node

2. Set the random pointer of the replicated node to the next node of the original node

3. Split the original linked list and the copied linked list. The copied linked list consists of all the copied nodes

The problem solving code

var copyRandomList = function(head) {
    // If the list is empty, return null
    if(! head)return null
    let p = head
    // Starting from the beginning, copy each node of the linked list and insert it between the current node and the next node
    while (p) {
        const newNode = new Node(p.val)
        newNode.next = p.next
        p.next = newNode
        p = p.next.next
    }
    p = head
    // Starting from the beginning node, point the random of the new node to the next node of the random of the original node
    while (p) {
        p.next.random = p.random ? p.random.next : p.random
        p = p.next.next
    }
    p = head
    // Define a virtual head node that points to the head node of the replication list
    const newHead = new Node(-1, p.next)
    // Split the original list and copy the list from the beginning node
    while(p) {
        const newNode = p.next
        p.next = p.next.next
        newNode.next = newNode.next ? newNode.next.next : null
        p = p.next
    }
    // Return the replication list
    return newHead.next
};
Copy the code