I am fried and happy that it is past 05:00 PM on a Friday evening. It was a long and busy week but to be honest with you, due to the lack of different activities during the day or evening, it seems that the days, weeks and months are passing faster than usual.
Tomorrow my wife and I will go grocery shopping at Cub Foods and Costco. On Sunday we will stop by Trader Joe’s. It seems that there is a better selection and quality of vegetables and fruits when comparing with most stores in this area.
I randomly (no pun intended) chose LeetCode problem 138 Copy List with Random Pointer. Since I am somewhat tired let’s go over the approach and code as fast as possible. My wife will be calling me up any time soon.
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where: val: an integer representing Node.val random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node. Constraints: o -10000 <= Node.val <= 10000 o Node.random is null or pointing to a node in the linked list. o The number of nodes will not exceed 1000.
The key of the problem is to understand what a deep copy is. LeetCode puts a link to the Wikipedia description. If you are not familiar with the concept please read the entire article. If you have been developing software for some time, I am sure you have the idea of what the problem is about. That said; please take a few minutes and read the article…
…OK. What we need to do is to make a copy of the linked list not using the memory that was used in the provided linked list. As you read the requirements and look at the examples, it all makes sense. You have probably used deep copy many times!
/*
// 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) {
}
}
The signature for the function / method we need to develop makes sense. We are given a linked list and we need to return a new linked list in which all elements are different than the ones used in the original linked list.
I will be developing the code in my Windows 10 computer using the Java programming language and the VSCode IDE. The good this of Java that in most (never generalize) cases it works in different machines without changes. That is why Java is so popular.
Since I will use my machine to develop the code, I need to generate a test scaffolding to read the input data and transformed to the argument we need to provide to the copyRandomList() function / method. The test program needs to call the function and display the results to make sure all is well.
In my case, once I feel confident all is well, I copy the function that is required by LeetCode into their IDE. The rest of the code in this post, which implements the test scaffolding, IS NOT PART OF THE SOLUTION.
[7,null],[13,0],[11,4],[10,2],[1,0] main <<< strArr: [7,null, 13,0, 11,4, 10,2, 1,0] main <<< head: (v: 7 r: null)->(v: 13 r: 7)->(v: 11 r: 1)->(v: 10 r: 11)->(v: 1 r: 7) main <<< ll: (v: 7 r: null)->(v: 13 r: null)->(v: 11 r: null)->(v: 10 r: null)->(v: 1 r: null) main <<< output: (v: 7 r: null)->(v: 13 r: 7)->(v: 11 r: 1)->(v: 10 r: 11)->(v: 1 r: 7) [1,1],[2,1] main <<< strArr: [1,1, 2,1] main <<< head: (v: 1 r: 2)->(v: 2 r: 2) main <<< ll: (v: 1 r: null)->(v: 2 r: null) main <<< output: (v: 1 r: 2)->(v: 2 r: 2) [3,null],[3,0],[3,null] main <<< strArr: [3,null, 3,0, 3,null] main <<< head: (v: 3 r: null)->(v: 3 r: 3)->(v: 3 r: null) main <<< ll: (v: 3 r: null)->(v: 3 r: null)->(v: 3 r: null) main <<< output: (v: 3 r: null)->(v: 3 r: 3)->(v: 3 r: null) [] main <<< strArr: [] main <<< head: main <<< ll: main <<< output:
The first line contains the test data for a case. All test data was obtained from LeetCode.
Our test scaffolding needs to read the data and generate the linked list to be offered to the function we need to develop.
It seems that we read the input line and split it into a string array that contains two pieces of data per node in the input linked list. The first component is the node value followed by the second which is the link to a random node (may also be null). Please note that there is nothing to do with this value but make sure that our deep copy list is able to reproduce it. The random link is not used to generate a new linked list. We are only interested in the value to make sure that the new copy of the link is consistent with the elements in the new linked list.
The next line displays the linked list which will be the argument we present to the function / method we need to implement as our solution.
The next line shows a copy of the linked list that was made disregarding the value of the random pointer. This is just an example of how could we approach the solution to generate a deep copy of the entire node.
Finally, the output for the problem is displayed. Note that three last lines contain the same elements at the same positions. The difference is that the middle line does not address the value for the random field.
OK, my wife asked me to stop working for the day… …Today is Saturday morning and I will finish this post.
Hint 1 Just iterate the linked list and create copies of the nodes on the go. Since a node can be referenced from multiple nodes due to the random pointers, make sure you are not making multiple copies of the same node.
LeetCode provides some hints for this problem. I open the first one and read it. I have not looked at the other hints yet. I will do so if I have issues developing the solution.
/**
* Definition for a Node.
*/
class Node {
// **** class members ****
int val;
Node next;
Node random;
// **** constructor ****
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
// **** ****
@Override
public String toString() {
String r = null;
if (this.random == null)
r = "null";
else
r = "" + random.val;
return "(v: " + this.val + " r: " + r + ")";
}
}
I have to implement the Node class because I am working on my computer. I added the last method for testing purpose only. It is not used in the actual solution.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read values for linked list ****
String str = br.readLine().trim();
// **** close buffered reader ****
br.close();
// **** remove start and end brackets ****
str = str.substring(1, str.length() - 1);
// **** split into pairs of values ****
String[] strArr = str.split("\\],\\[");
// ???? ????
System.out.println("main <<< strArr: " + Arrays.toString(strArr));
// **** build linked list of nodes ****
Node head = buildLinkedList(strArr);
// ???? display linked list ????
System.out.print("main <<< head: ");
display(head);
System.out.println();
// **** deep copy of linked list (no random pointers) ****
Node ll = copyLinkedList(head);
// ???? display deep copy linked list ????
System.out.print("main <<< ll: ");
display(ll);
System.out.println();
// **** deep copy of linked list (include random pointers) ****
Node dc = copyRandomList(head);
// ???? display deep copy linked list ????
System.out.print("main <<< output: ");
display(dc);
System.out.println();
}
This is the test code scaffolding. IT IS NOT PART OF THE SOLUTION. We start by opening a buffered reader, read the line for the node values in the linked list, and then close the buffered reader. We do not need to input additional data.
We then remove the ‘[‘ and the ‘]’ characters from the string. I could have not included them in the input line, but it was included by LeetCode. The input line is then displayed.
We then take the array and generate the linked list that we will pass to the function we need to develop. The linked list is then displayed.
We then call the copyLinkedList() function / method which will use to experiment with the approach we will use in the actual solution. We will discuss it in more detail in a few. The resulting linked list is displayed. Note that the random fields are not filled at this time. This is indicated by the null in the second value of each node.
We are now ready to generate the result by implementing the copyRandomList() function / method. As expected, we pass the head of the linked list and get back a deep copy version of a new list. The new list is then displayed.
/**
* Build linked list from specified array of strings.
* Execution time: O(n)
*
* !!! NOT PART OF SOLUTION !!!
*/
static Node buildLinkedList(String[] strArr) {
// **** sanity check(s) ****
if (strArr == null || strArr[0].equals(""))
return null;
// **** initialization ****
Node[] nodes = new Node[strArr.length];
Integer[] randoms = new Integer[strArr.length];
Node head = null;
Node tail = head;
// **** traverse array of strings O(n) ****
for (int i = 0; i < strArr.length; i++) {
// **** split ****
String[] s = strArr[i].split(",");
// **** extract val ****
int val = Integer.parseInt(s[0]);
// **** extract random index ****
Integer randIndex = null;
if (!s[1].equals("null"))
randIndex = Integer.parseInt(s[1]);
// **** save random reference ****
randoms[i] = randIndex;
// **** create node ****
Node node = new Node(val);
// **** insert node to list (at tail) ****
if (head == null) {
head = node;
tail = node;
} else {
tail.next = node;
tail = node;
}
// **** save the node in the array ****
nodes[i] = node;
}
// **** set random field in all nodes O(n) ****
for (int i = 0; i < nodes.length; i++) {
if (randoms[i] != null)
nodes[i].random = nodes[randoms[i]];
}
// **** return head of linked list ****
return head;
}
The buildLinkedList() function / method is used to build the linked list we need to pass as an argument. In the first loop we populate the list leaving the random field in each node set to the default value which is null. Note that we keep track of the nodes and the positions in the list for the nodes to which the random field is pointing as provided by the input line. In the second loop we update the random fields in all the nodes. Finally, the linked list is returned to the caller.
/**
* Display linked list.
*
* !!! NOT PART OF SOLUTION !!!
*/
static void display(Node head) {
// **** sanity check(s) ****
if (head == null)
return;
// **** traverse the link list ****
for (Node p = head; p != null; p = p.next) {
System.out.print(p.toString());
if (p.next != null)
System.out.print("->");
}
}
This function is used to display the linked lists we are processing. We just perform a traversal and for each node we display the values of the node and random fields.
/**
* Return a deep copy of the linked list.
* Does not include random pointer.
*
* !!! NOT PART OF SOLUTION !!!
*/
static Node copyLinkedList(Node head) {
// **** sanity check(s) ****
if (head == null)
return null;
// **** initialization ****
HashMap<Node, Node> hm = new HashMap<>();
Node q = new Node(head.val);
hm.put(head, q);
Node ll = q;
// **** traverse the linked lists O(n) ****
for (Node p = head; p != null; p = p.next, q = q.next) {
// **** store reference (pointer) ****
Node nextNode = p.next;
// **** create & update next pointer (if needed) ****
if (nextNode != null) {
// **** create new next node (if needed) ****
if (!hm.containsKey(nextNode)) {
hm.put(nextNode, new Node(nextNode.val));
}
// **** point to next node ****
q.next = hm.get(nextNode);
}
}
// **** return deep copy of linked list ****
return ll;
}
The copyLinkedList() function generates a copy of the provided linked list as an argument. Note that we are creating new nodes. We are not just creating references to the nodes in the original linked list.
For a typical approach we could just traverse the original linked list. For each node we create a new one and append it to the new linked list.
In this function we use a hash map to store the original node as a key and the new node as a value. The key is the node in the original linked list, while the value is the node created for the copy of the linked list. This is not needed for a typical copy, but keep in mind we ARE NOT dealing with the random filed at all.
The loop is used to traverse the list using the p pointer. The q pointer is just used to get to the next node.
Take a few moments and make sure you can follow what seems to be a convoluted way of getting accomplished what we need at the time.
The hash map is used to create the next node which will be used in the next pass of the loop.
When done we return the deep copy of the linked list.
/**
* Return a deep copy of the list.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.7 MB, less than 58.54% of Java online submissions
*/
static Node copyRandomList(Node head) {
// **** sanity check(s) ****
if (head == null)
return null;
// **** initialization ****
HashMap<Node, Node> hm = new HashMap<>();
Node q = new Node(head.val);
hm.put(head, q);
Node dc = q;
// **** traverse the linked lists O(n) ****
for (Node p = head; p != null; p = p.next, q = q.next) {
// **** store pointers (references) ****
Node randNode = p.random;
Node nextNode = p.next;
// **** create & update random pointer (if needed) ****
if (randNode != null) {
// **** create new random node (if needed) ****
if (!hm.containsKey(randNode)) {
hm.put(randNode, new Node(randNode.val));
}
// **** point to next random node ****
q.random = hm.get(randNode);
}
// **** create & update next pointer (if needed) ****
if (nextNode != null) {
// **** create new next node (if needed) ****
if (!hm.containsKey(nextNode)) {
hm.put(nextNode, new Node(nextNode.val));
}
// **** point to next node ****
q.next = hm.get(nextNode);
}
}
// **** return pointer to deep copy ****
return dc;
}
Finally we get to the function that is required by LeetCode. Note the similarities with the previous function.
Instead of just addressing the nextNode we also address, in a similar fashion, the value for the random pointer.
By using this approach we can generate a deep copy of an object in O(n) time.
I enjoyed this problem. In my opinion it was not so simple to come up with a solution. In general singly linked lists are seldom used in solving real word problems. The purpose of this exercise is to understand the difference between a reference to a previous object and how to generate the reference to the new object. This was demonstrated by updating the random pointer in the new linked list (the one named dc).
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 5,106 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
Regards;
John
john.canessa@gmail.com