Copy linked list with random pointer [space for time --hash record]

Preface

Space for time is a very common way to reduce time complexity , and hashMap/hash Array / Binary system hash Is the usual way .

One 、 Copy list with random pointer

Two 、hash Record

package everyday.hash;

import java.util.HashMap;
import java.util.Map;

public class CopyRandomList {
    
    public Node copyRandomList(Node head) {
    
        //  Set up dummy node , Take the special case head==null, As well as the head node problem .
        Node dummyHead = new Node(1);
        dummyHead.next = head;
        Node cloneDummyHead = new Node(1);
        //  Record the original node and the newly generated node mapping .
        Map<Node, Node> fx = new HashMap<>();
        //  Set the head node and the walk node .
        Node p = dummyHead.next;
        Node cur = cloneDummyHead.next;
        //  Set up next
        while (p != null) {
    
            //  Generate new nodes 
            Node next = new Node(p.val);
            //  Record old and new node mappings , Set... For the back random Prepare the pointer .
            fx.put(p, next);
            //  Set new linked list next
            cur.next = next;
            //  to update cur/p
            cur = cur.next;
            p = p.next;
        }
        //  Set up random
        p = dummyHead.next;
        cur = cloneDummyHead.next;
        while (p != null) {
    
            //  obtain cur node random Point to .
            Node random = fx.get(p.random);
            //  Set up random
            cur.random = random;
            //  to update cur/p
            cur = cur.next;
            p = p.next;
        }
        //  Return the cloned linked list 
        return cloneDummyHead.next;
    }

    // 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;
        }
    }
}

summary

1） Space for time ,hashMap/hashSet/hash Array / Binary system hash

reference

[1] LeetCoed Copy list with random pointer