Hello, today I come to share a linked list problem

138. copy linked list with random pointer from force link

At first glance, this topic seems to be a copy of the linked list, which is very simple. However, the node structure of this linked list is different from that of the usual linked list, because there is an extra random pointer to point to, so there will be another link to deal with

First, assume the linked list as shown in the figure (the node values are not set as numbers, but are set as letters for easy identification and numbers are easy to confuse).

Node A: the value is A, and the next node is B, and the random pointer points to: node C node B: the value is B, and the next node is C, and the random pointer points to: node B

First step: copy each node, copy the value of the current node and the next of the node, chain the linked list, and finally form the following linked list (copyA equals A to distinguish the prefix and copy to distinguish the nodes).

Step 2: Copy the random pointer of the copied node

Step 3: Disconnect the pointer between the copied node and the original node, so that the next of the copied node points to the copied node, and the final result is the copied linked list with random Pointers

The code is as follows:

var copyRandomList = function(head) {
    if (head === null) {
        return null;
    }
    // Step 1: Copy the node and initialize random to NULL
    let node1 = head
    while(node1){
        let nodeNew = new Node(node1.val,node1.next,null)
        node1.next = nodeNew
        node1 = node1.next.next
    }
    
    // Step 2: Copy the current random to the random of the copied node
    let node2 = head 
    while(node2){
        let nodeNew = node2.next // nodeNew is the replicated node
        // node2.random. Next is the next pointer to the existing random pointer,
        // the random pointer to node A points to node C, which is the next node of node C, copyC nodenodeNew.random = (node2.random ! = =null)? node2.random.next :null
        node2 = node2.next.next // The currently copied node completes and bypasses the two nodes that just operated
    }
    
    // Step 3: Copy the pointer link between nodes and disconnect the pointer of the original node
    const headNew = head.next; // This bypasses the first replicated node directly
    let node3 = head
    while(node3){
        let nodeNew = node3.next // Here is the first replicated node
        node3.next = node3.next.next // Change the current replicated node before the next replicated node
        // If the next node of the replicated node is not null, there must be another node copied from the next nodenodeNew.next = nodeNew.next ! = =null ? nodeNew.next.next : null
        node3 = node3.next// Switch the node to the next replicated node to continue the illusion
    }
    return headNew;
};
Copy the code

Finally, the following figure shows the execution process

That’s all for sharing