The title

Copy of complex linked lists

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

Analysis:

The difficulty lies in how to copy the random pointer of a node. If you copy a random directly, you will not know whether the random has been created. To know if Random has been created, you can use a hash table to store a mapping between the current node and the copied node.

Idea 1:

Hash table + iteration

  1. First, the original linked list is traversed, and all nodes are copied and stored in the hash table. Key is the original node, value is the replicated node, and next and Random are temporarily copied to NULL
  2. Iterate through the original linked list again and assign next and random Pointers to the copied nodes. The source of the Pointers is: [Next and Random nodes to which the original node points map the corresponding copied nodes in the hash table]

The specific code is as follows:

/ * * *@param {Node} head
 * @return {Node}* /
var copyRandomList = function(head) {
    let cur = head;
    let hashMap = new Map(a);while(cur){
        hashMap.set(cur,new Node(cur.val,null.null));
        cur = cur.next;
    }

    cur = head;
    while(cur){
        hashMap.get(cur).next = cur.next ? hashMap.get(cur.next) : null;
        hashMap.get(cur).random = cur.random ? hashMap.get(cur.random) : null;
        cur = cur.next;
    }
    return hashMap.get(head);
}

Copy the code

Idea 2:

Splicing + shearing

Copy a set of link nodes, and then make the old and new nodes stagger together in turn. When we visit and find a new node random, we can go to the next of the previous original node random of the new node

  1. Next = newNode,newNode.next = cur.next. Next;
  2. Iterate over the original list and copy the next of the node whose random points to the original node to the new node, that is, cur.next. Random = cur.random. Next
  3. Walk through the old list and cut the links between the old and new lists.

The code is as follows:

/ * * *@param {Node} head
 * @return {Node}* /
var copyRandomList = function(head) {
    if(head==null)return head;
    let cur = head;
    while(cur){
        let tmp = new Node(cur.val,null.null);
        tmp.next = cur.next;
        cur.next = tmp;
        cur = cur.next.next;
    }

    cur = head;
    while(cur){
        cur.next.random = cur.random ? cur.random.next : null;
        cur = cur.next.next;
    }

    cur = head.next;
    let pre = head,res = head.next;
    while(cur.next){
        pre.next = pre.next.next;
        cur.next = cur.next.next;
        pre = pre.next;
        cur = cur.next;
    }
    pre.next = null;
    return res
}
Copy the code

Idea 3:

Hash table plus recursion

This one is a little bit harder to understand because of the recursion, but it’s the simplest.

  1. Defines a recursive function whose incoming parameters are the old node and hash table, and outgoing parameters are the new node
  2. Check whether a new node has been created for the original node. If yes, it will return directly. If no, it will start to create
  3. Copy the original node to create a new node, nex and random are assigned null, and the original node is the key, and the new node is the value of the hash table
  4. Copy the next pointer for the new node, with the value of the recursive call itself to find or create in the hash table.
  5. Copy the random pointer for the new node, with the value for the recursive call itself to find or create in the hash table.

You can write your own simple demo to digest it step by step

The code is as follows:

/ * * *@param {Node} head
 * @return {Node}* /
var copyRandomList = function(head,cacheNode = new Map(a)) {
    if(head==null)return head;
    if(! cacheNode.get(head)){ cacheNode.set(head,{val:head.val})
        cacheNode.get(head).next = copyRandomList(head.next,cacheNode)
        cacheNode.get(head).random = copyRandomList(head.random,cacheNode)
    }
    return cacheNode.get(head);
}

Copy the code