Hi gals and guys. Hope you are doing well during the COVID-19 pandemic. It seems that most of us are somewhat tired following the basic rules that reduce the spread of the coronavirus. By relaxing the rules in the past few months, the numbers of COVID-19 infections, in most cities worldwide, are going up. Note that the issue is the number of infections, not the number of deaths. Infected people may need hospital services. If the number of patients is larger than the capacity like it was when this thing started, then we have a problem. At this point in time, people with most infections per 1,000, is people in college age. Please follow the rules! We all benefit from it.
Earlier today I picked LeetCode problem 1265 Print Immutable Linked List in Reverse. I learned something interesting. Before I touch on it lets look at the problem description and my three approaches.
As usual, I like to develop the solution on my machines. Due to this, I have to 
develop a test scaffolding to accept the data and get it ready to pass it to the function / method which represents the entry point for the problem.
Today I will use the Java programming language and the VSCode IDE running on a Windows 10 computer. At some point I was working on a different machine and the machine I am writing the post decided to install an update. I am not exaggerating when I say that the update took more than 3 hours!
You are given an immutable linked list, print out all values of each node in reverse with the help of the following interface: ImmutableListNode: An interface of immutable linked list, you are given the head of the list. You need to use the following functions to access the linked list (you can't access the ImmutableListNode directly): ImmutableListNode.printValue(): Print value of the current node. ImmutableListNode.getNext(): Return the next node. The input is only given to initialize the linked list internally. You must solve this problem "without modifying" the linked list. In other words, you must operate the linked list using only the mentioned APIs. Constraints: o The length of the linked list is between [1, 1000]. o The value of each node in the linked list is between [-1000, 1000]. Follow up: Could you solve this problem in: o Constant space complexity? o Linear time complexity and less than linear space complexity?
The requirements for the problem are simple to understand. We are provided a linked list and our task, if we wish to accept, is to print the elements in reverse order. The problem seems to call for a stack. We can push elements into it and then pull them back in reverse order.
With that in mind, I went and read the full description of the requirements a couple times. We can give a try to the stack as a first pass and then we can go with a recursive approach. Sounds like a plan.
/**
* // This is the ImmutableListNode's API interface.
* // You should not implement it, or speculate about its implementation.
* interface ImmutableListNode {
* public void printValue(); // print the value of this node.
* public ImmutableListNode getNext(); // return the next node.
* };
*/
class Solution {
public void printLinkedListInReverse(ImmutableListNode head) {
}
}
The plot thickens. In addition to a linked list, we are only able to use a couple methods from the class as defined by the specified interface. We have to provide to the printLinkedListInReverse() method the head of the queue. Since we are going to develop the test scaffolding, we need to read the data and populate the queue so we can then pass the head to the entry point method.
1,2,3,4 main <<< arr: [1, 2, 3, 4] main <<< head -> 1 -> 2 -> 3 -> 4 main <<< reverse: 4 3 2 1 main <<< reverse: 4 3 2 1 main <<< reverse: 4321 0,-4,-1,3,-5 0,-4,-1,3,-5 main <<< arr: [0, -4, -1, 3, -5] main <<< head -> 0 -> -4 -> -1 -> 3 -> -5 main <<< reverse: -5 3 -1 -4 0 main <<< reverse: -5 3 -1 -4 0 main <<< reverse: -53-1-40 -2,0,6,4,4,-6 main <<< arr: [-2, 0, 6, 4, 4, -6] main <<< head -> -2 -> 0 -> 6 -> 4 -> 4 -> -6 main <<< reverse: -6 4 4 6 0 -2 main <<< reverse: -6 4 4 6 0 -2 main <<< reverse: -64460-2
The output from our test scaffolding seems to read in the data into an array, then populates a queue and displays it to make sure all is well before calling the method in question. It seems that we have three implementations. They all produce the same results. The deference is the way the reversed notes are displayed. Remember that displaying results is part of the solution and input and in this case output is very slow when compared to processing.
/**
* This is the ImmutableListNode's API interface.
* You should not implement it, or speculate about its implementation.
*/
interface ImmutableListNodeIn {
public void printValue(); // print the value of this node.
public ImmutableListNodeIn getNext(); // return the next node.
};
This is the interface provided by LeetCode we should use for our solution. If you solve the problem on-line you do not need to worry about creating a test scaffolding. In our case we have to deal with the interface and the class that implements it.
/**
* Class implementation.
* Not part of the solution!!!
* Part of the test scaffolding.
*/
class ImmutableListNode implements ImmutableListNodeIn {
// **** ****
public int val;
public ImmutableListNode next;
// **** constructor ****
public ImmutableListNode(int val) {
this.val = val;
this.next = null;
}
// **** print value of node****
@Override
public void printValue() {
System.out.print(this);
}
// **** get next node ****
@Override
public ImmutableListNode getNext() {
return this.next;
}
// **** ****
@Override
public String toString() {
return "" + val;
}
}
I implemented the ImmutableListNode class with the interface suggested by LeetCode. This is not part of the solution.
I decided to implement the printValue() and getNext() methods the way that I would expect them to operate. I had to add the constructor because I have to populate the queue. In addition I added a way to print the node since that is one of the two methods we must use.
/**
* Test scaffolding
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read line with node values ****
String[] strs = sc.nextLine().trim().split(",");
// **** close scanner ****
sc.close();
// **** ****
int[] arr = new int[strs.length];
for (int i = 0; i < strs.length; i++) {
arr[i] = Integer.parseInt(strs[i]);
}
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** populate the linked list ****
ImmutableListNode head = populate(arr);
// ???? ????
System.out.print("main <<< head");
for (ImmutableListNode p = head; p != null; p = p.next) {
System.out.print(" -> " + p.toString());
}
System.out.println();
// **** print linked list in reversed order ****
System.out.print("main <<< reverse: ");
printLinkedListInReverse0(head);
System.out.println();
// **** print linked list in reversed order ****
System.out.print("main <<< reverse: ");
printLinkedListInReverse1(head);
System.out.println();
// **** print linked list in reversed order ****
System.out.print("main <<< reverse: ");
printLinkedListInReverse(head);
System.out.println();
}
The test scaffolding seems to be as expected. We open a scanner and read the line with the values separated by ‘,’s and split them into individual strings. We then close the scanner, create an array of integers and populate the array. With the array we populate the queue.
At this point we are ready to call the entry point method. In our case we call three implementations which we will discuss one at a time.
/**
* Auxiliary function.
* Not part of the solution!!!
* Part of the test scaffolding.
*/
static ImmutableListNode populate(int[] arr) {
// **** sanity checks ****
if (arr.length == 0)
return null;
// **** allocate head node ****
ImmutableListNode head = new ImmutableListNode(arr[0]);
ImmutableListNode tail = head;
// **** ****
for (int i = 1; i < arr.length; i++) {
// **** allocate node ****
ImmutableListNode node = new ImmutableListNode(arr[i]);
// **** insert node at tail of queue ****
tail.next = node;
// **** update tail ****
tail = node;
}
// **** return the head of the list ****
return head;
}
The populate() method is not part of the solution. I had to populate the queue so had to implement a method to do so. We create the head node and enter a loop. In the loop we allocate nodes and insert them into the queue. When done we return the head of the queue.
/**
* The head to the queue is provided.
* Approach using a stack.
*
* Runtime: 8 ms, faster than 6.02% of Java online submissions.
* Memory Usage: 39 MB, less than 17.14% of Java online submissions.
*/
static void printLinkedListInReverse0(ImmutableListNode head) {
// **** initialization ****
Stack<ImmutableListNode> stack = new Stack<>();
// **** push the head of the queue into the stack ****
stack.add(head);
// **** push all queue nodes into the stack ****
ImmutableListNode node = head;
while ((node = node.getNext()) != null) {
stack.add(node);
}
// **** pop the stack printing the values ****
while (!stack.isEmpty()) {
node = stack.pop();
node.printValue();
System.out.print(" ");
}
}
This is the first implementation of a solution. We use a stack. We push into the head of the queue. Then we enter a while loop in which we traverse the queue and push each node into the stack.
When done, the stack holds all the queue elements in reverse order.
The second and last loop is used to pop elements from the stack and print them. After each element is popped from the stack we display it and followed the value by a ‘ ‘ in order to be able to read them. I like to be able to be able to read data in the simplest possible way and still comply with requirements. Please note that the output for the examples is in the LeetCode web page and it is not what is expected; it is only a guideline.
The performance of this method is not that great. We will now try a different approach.
/**
* The head to the queue is provided.
* Recursive approach.
*
* Runtime: 9 ms, faster than 6.02% of Java online submissions.
* Memory Usage: 39 MB, less than 17.14% of Java online submissions.
*/
static void printLinkedListInReverse1(ImmutableListNode head) {
// **** base condition ****
if (head == null) {
return;
}
// **** recursive case ****
printLinkedListInReverse1(head.getNext());
// **** print node value ****
head.printValue();
// **** print separator ****
System.out.print(" ");
}
This is a recursive method. We have a base condition that tells us when to stop recursion.
The recursive case is used to get to the end of the queue one node at a time. This is accomplished by calling the recursive method with the next element in the queue.
After we reach the end of the recursion, we pint the value of the last node. This is the start of printing the values in reverse order. As in the previous method, we display a separator so we can better read the numbers. Please note that displaying is a time consuming operation.
Take a look at the execution time. Not much had changed except the use of less memory for the stack.
While I was experimenting with ‘,’ and spaces, I decided to just display values without separators.
/**
* The head to the queue is provided.
* Recursive approach.
* No separators.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 37.8 MB, less than 71.82% of Java online submissions.
*/
static void printLinkedListInReverse(ImmutableListNode head) {
// **** base case ****
if (head == null) {
return;
}
// **** recursive case ****
printLinkedListInReverse(head.getNext());
// **** print node value ****
head.printValue();
}
This recursive method is identical to the previous one. The only difference is that it does not display a separator between values. Take a look at the runtime. It is the fastest implementation for this problem!
From now on I will not spend time in making the results readable. I will only concentrate on the actual values. If the test requires something different, then I will address the issue on a case by case.
To be honest with you, I do not develop software to get the fastest solution. I like the most elegant and easy to understand and maintain.
So there you have it, I learned something new today!
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 4,387 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
john.canessa@gmail.com