Title:

Implement the copyRandomList function to copy a complex chain list. In a complex chain table, each node has a next pointer to the next node, and a random pointer to any node or null in the chain table.

for example

 

 

 

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

 

Ideas:

I didn't think about the topic at first, but I realized later that I was really not good at citing typology. Defining a new node assigns a value using the old chain table, but adds a reference to the node of the old chain table, not duplicates it.

True replication should be a new, empty node that assigns a val ue to the original list of chains, while next and random must also point to the node they create.

Here you can make it clear that the list needs to be traversed at least twice. Because the nodes pointed to randomly may not have been created when a new chain table node is first created, it is necessary to string all the nodes of the new chain table before the updated random direction can be traversed again.

So the problem is how to reproduce the node relationship of the old list in the two new nodes of the new list?

A represents the new list node, B represents the old list node, that is, the corresponding relationship between A.random and B.random needs to be found. Further thought, the problem can be solved by simply having the relationship mapping of each node of A table to its corresponding B table node, so HashMap can be thought of.

While traversing to create the B table, the corresponding relationship of AB exists in the map with the A table node as the key and the B table node as the value. The second iteration updates the random pointer by simply taking out the B corresponding to A and assigning the B node corresponding to A.random to B.random

The code is as follows:

/*
// 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) {
        // Processing boundary values
        if (head == null) {
            return null;
        }
        Map<Node, Node> nmap = new HashMap<>();
        Node newHead = new Node(head.val);
        Node curNode = head;
        nmap.put(head, newHead);
        // Generating Base Chain List and Mapping map
        while (curNode.next != null) {
            // Generate a new node
            Node newNode = new Node(curNode.next.val);
            // Remove the previous node
            Node preNode = nmap.get(curNode);
            // Connect the new node to the previous node;
            preNode.next = newNode;
            // stay map Update the previous node in the
            nmap.put(curNode.next, newNode);
            curNode = curNode.next;
        }
        // To update random Pointer
        curNode = head;
        while (curNode != null) {
            // query random node
            Node randomNode = curNode.random;
            if (randomNode != null) {
                nmap.get(curNode).random = nmap.get(randomNode);
            } else {
                nmap.get(curNode).random = null;
            }
            curNode = curNode.next;
        }
        return newHead;
    }
}

 

Summary:

Of course, there are more bulls, using less space, using the stitching/splitting chain table method to answer, the code is as follows:

/*
// 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;
    }
}
*/
//Stitching+split
/**
1 Copy each node to build a stitching chain table:
Set the original chain table as node1_node2, and construct the splice chain table as follows:
node1→node1 new→node2→node2 new→⋯

2 Construct the random pointing of each node in the new list:
When the cur of the original node is visited randomly, it points to the cur of the node. When random, cur corresponds to the new node. Next's random pointing node is cur.random.next.

3  Split the original/new list:
Set pre/cur to point to the original/new chain header node, traverse to execute pre.next = pre.next.next and cur.next = cur.next.next splits the two lists.
Return the header res of the new list.

 */
class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) return null;
        Node cur =head;
        //1 Duplicate each node to build a stitching chain table
        while(cur!=null){
            Node tmp=new Node(cur.val);
            tmp.next=cur.next;
            cur.next=tmp;
            cur=tmp.next;
        }
        //2 Build a new list of nodes random point
        cur=head;
        while(cur!=null){
            if(cur.random!=null){
                cur.next.random=cur.random.next;
            }
            cur=cur.next.next;
        }
        //3 Splitter / New Chain List
        cur=head.next;
        Node pre=head,res=head.next;
        while(cur.next!=null){
            pre.next=pre.next.next;
            cur.next=cur.next.next;
            pre=pre.next;
            cur=cur.next;
        }
        pre.next=null;//Processing the end of the original list separately
        return res;
    }
}

Standard answer, learn one.

It is through "own next is their own copy", to achieve the management of mapping relationship, very strong!