Java Algorithms: Copying List with Random Pointer (LeetCode)

A linked listing of size n is given such that every node accommodates an extra random pointer, which may level to any node within the listing, or null.

Assemble a deep copy of the listing. The deep copy ought to encompass precisely n model new nodes, the place every new node has its worth set to the worth of its corresponding authentic node. Each the subsequent and random pointer of the brand new nodes ought to level to new nodes within the copied listing such that the pointers within the authentic listing and copied listing symbolize the identical listing state. Not one of the pointers within the new listing ought to level to nodes within the authentic listing.

For instance, if there are two nodes X and Y within the authentic listing, the place X.random --> Y, then for the corresponding two nodes x and y within the copied listing, x.random --> y.

Return the pinnacle of the copied linked listing.

The linked listing is represented within the enter/output as a listing of n nodes. Every node is represented as a pair of [val, random_index] the place:

• val: an integer representing Node.val

• random_index: the index of the node (vary from 0 to n-1) that the random pointer factors to, or null if it doesn’t level to any node.

Your code will solely be given the head of the unique linked listing.

Instance 1:

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

Instance 2:

Enter: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Instance 3:

Enter: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints:

• 0 <= n <= 1000
• -104 <= Node.val <= 104
• Node.random is null or is pointing to some node within the linked listing.

Reasoning:

For the primary look this activity appears to be like like onerous one though in actuality it isn’t. However it has one property which we have to take note of and construct a behavior round it. Everytime you see an issue which may be divided into smaller issues — divide it. It’s one of many important patterns you’ll be able to apply to nearly any downside. Let me assist you with this. Let’s reread the duty once more and divide it into smaller subproblems.

1. We have to create a replica of every node with the identical worth as authentic one.

2. We have to set tips to the following node the identical method as in authentic one

3. We have to set tips to the random node the identical method as in authentic one+

You’ll be able to say at this level, wait as a substitute of getting one downside now we’ve got 3. Sure you’re proper however they’re much simpler to unravel. Let’s bounce to the answer part and I’ll show it to you.

Prerequisite:

If you wish to debug your code, which I personally suggest, you need to introduce this class

class Node

   int val;
   Node subsequent;
   Node random;

   public Node(int val)
   
      this.val = val;
      this.subsequent = null;
      this.random = null;
   

Answer:

Let’s begin from fixing the primary subproblem. Let’s do easy factor iterate via linked listing and create a replica for each node in it. I select HashMap for storing pairs like outdated node -> new node. So long as we’re going to iterate from head of the listing to tail let’s additionally introduce temp variable and set it to be the pinnacle of the listing.

Map<Node, Node> map = new HashMap<>();
Node temp = head;
whereas (temp != null)

   map.put(temp, new Node(temp.val));
   temp = temp.subsequent;

We solved the primary subproblem. You’ll be stunned how straightforward we are able to remedy the following two. We have already got connections between outdated nodes and new ones. We solely must populate tips to subsequent node and random pointer. Our map already shops all the data we want. Let’s once more set temp to be the pinnacle of the listing. Let’s additionally introduce new dummy node which can be storing hyperlink to our freshly copied head. The very last thing we want is prev pointer which is able to assist us to arrange relationship node -> subsequent node

Our options ought to appear like this

public Node copyRandomList(Node head)

   Map<Node, Node> map = new HashMap<>();
   Node temp = head;
   whereas (temp != null)
   
      map.put(temp, new Node(temp.val));
      temp = temp.subsequent;
   

   temp = head;
   Node dummy = new Node(0);
   Node prev = dummy;
   whereas (temp != null)
   
      prev.subsequent = map.get(temp);
      map.get(temp).random = map.get(temp.random);

      prev = prev.subsequent;
      temp = temp.subsequent;
   

   return dummy.subsequent;

The code above offers us linear time and house complexity.

Additionally revealed here.