In the past three days the high for the day has been in the mid to upper 40s. Since late fall a considerable amount of leaves has been accumulating in the entrance at home. Yesterday just before lunch I picked up the dead leaves. This morning some started to collect. I guess this is due to the orientation and shape of the entrance.
Last evening I also read an interesting article titled After Centuries, a Seemingly Simple Math Problem Gets an Exact Solution by Steve Nadis published in Quanta Magazine. Apparently a German mathematician named Ingo Ullisch figured out an exact solution for a problem. Good for him. What I liked more than the problem or its solution is the last paragraph in the article. In my humble opinion, this reaffirms the fact that reading and experimenting is the best way to learn.
This is an interesting problem posted by Facebook on the coding practice web site. The title is Reverse Operations. If interested please visit the site and read all about it.
The title is interesting. The idea is to undo (reverse) what was done to a linked list. The title has little to do with the task at hand. I guess that makes it harder to look for similar problem on other sites (i.e., HackerRank, LeetCode) where you can solve a problem, have it tested with dozens of test cases, and when done check if your solution is good enough or look at the best ones and learn from them. Of course, that is not the intention of this site.
You are given a singly-linked list that contains N integers.
A subpart of the list is a contiguous set of even elements,
bordered either by either end of the list or an odd element.
For example, if the list is [1, 2, 8, 9, 12, 16],
the subparts of the list are [2, 8] and [12, 16].
Then, for each subpart, the order of the elements is reversed.
In the example, this would result in the new list, [1, 8, 2, 9, 16, 12].
The goal of this question is:
given a resulting list, determine the original order of the elements.
Implementation detail:
You must use the following definition for elements in the linked list:
class Node {
int data;
Node next;
}
Constraints:
o 1 <= N <= 1000, where N is the size of the list
o 1 <= Li <= 10^9, where Li is the ith element of the list
We are given a singly-linked list containing a number of nodes with integers. The list may or may not have sets of contiguous even numbers. The sub-sets may be terminated by an odd integer or the end of the linked list.
Apparently we need to reverse the order of the even sub-sets inside the linked list. It seems that the same problem could be described to do exact the same thing for the first time. The results would be switching from original to modified, and vice versa. I would not be surprised that we could find the same problem with a different name. If you do, please send me a message. Would like to test the code I wrote and see how others would approach the problem.
I have written and maintained libraries that deal with queues and stacks. I always have a hard time remembering where is the head located, and where is the tail. In other words, do you insert on one end or the other and vice versa. Keep in mind that current implementations allow to insert and remove from either end, both on stacks and queues. Not only that but you have methods to insert and remove elements in between. If you have doubts on what is a linked list or a FIFO you can find some information in Wikipedia.
Node reverse(Node head) {
}
I will solve this problem using Java on a Windows 10 computer using the VSCode IDE. Given that the problem is addressed in Java it should run on any machine with a Java engine.
1,2,8,9,12,16 main <<< arr: [1, 2, 8, 9, 12, 16] main <<< populate: 1->2->8->9->12->16 main <<< reverse: 1->8->2->9->16->12 main <<< reverseList: 16->12->9->8->2->1 1,2,8,9,12,16,19 main <<< arr: [1, 2, 8, 9, 12, 16, 19] main <<< populate: 1->2->8->9->12->16->19 main <<< reverse: 1->8->2->9->16->12->19 main <<< reverseList: 19->16->12->9->8->2->1 2,4,8,9,12,16 main <<< arr: [2, 4, 8, 9, 12, 16] main <<< populate: 2->4->8->9->12->16 main <<< reverse: 8->4->2->9->16->12 main <<< reverseList: 16->12->9->8->4->2 2,1,3,4,6,5,7,9,10,12,14 main <<< arr: [2, 1, 3, 4, 6, 5, 7, 9, 10, 12, 14] main <<< populate: 2->1->3->4->6->5->7->9->10->12->14 main <<< reverse: 2->1->3->6->4->5->7->9->14->12->10 main <<< reverseList: 14->12->10->9->7->5->6->4->3->1->2 1 main <<< arr: [1] main <<< populate: 1 main <<< reverse: 1 main <<< reverseList: 1
Since I am solving the problem on my computer I need to prepare a test scaffolding.
The first line (input) contains the integer values used to populate the linked list.
The second line displays the values in an integer array. This was done to make sure all is well so far. We then create and populate a linked list.
Then it appears that we call the function we need to implement and display the returned linked list. As you can see the even numbers have been reversed.
The following line has nothing to do with the solution. It shows the original linked list after all elements have been reversed. Some time ago I wrote the post Reverse Linked List in which I generated a solution to reversing a list from head to tail using a recursive approach. For the problem at hand I first used an iterative approach. Since it conforms to the sample and passed the two provided tests, I would assume it is correct.
I decided to think about a recursive solution. To warm up I implemented the reverse of a complete linked list. I do not have it in this post, but I started with an alternate implementation and ran out of time. If you are interested please take a look at my GitHub repository.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read line and split into array of Strings ****
String[] strs = br.readLine().trim().split(",");
// **** close buffered reader ****
br.close();
// **** create and populate integer array ****
int[] arr = Arrays.stream(strs)
.mapToInt(Integer::parseInt)
.toArray();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// ***** create and populate linked list ****
Node head = populate(arr);
// ???? ????
System.out.print("main <<< populate: ");
traverse(head);
// **** reverse linked list ****
head = reverse(head);
// ???? ????
System.out.print("main <<< reverse: ");
traverse(head);
// ***** create and populate linked list ****
head = populate(arr);
// **** reverse entire linked list recursively ****
head = reverseList(head);
// ???? ????
System.out.print("main <<< reverseList: ");
traverse(head);
// // ***** create and populate linked list ****
// head = populate(arr);
// // **** reverse even elements in linked list ****
// head = revEven(head);
// // **** display reversed linked list ****
// System.out.print("main <<< revEven: ");
// traverse(head);
}
We read the input line, split the string and create and populate an integer array with the values for the nodes in the linked list.
We then create and populate a linked list. We display the linked list to make sure all is well so far.
We then reverse the linked list as specified in the requirements section of the problem and display the updated linked list. That is it for the problem and solution.
In addition I implemented a reversal of an entire linked list. The idea was to use it as the base for an alternate approach. As I mentioned earlier, I ran out of time.
/**
* Reverse even nodes in linked list.
*/
static Node reverse(Node head) {
// **** sanity checks ****
if (head == null || head.next == null)
return head;
// **** initialization ****
Stack<Node> stack = new Stack<Node>();
Node q = null;
Node r = null;
// **** traverse the linked list O(n) ****
for (Node p = head; p != null; ) {
// **** skip nodes with odd data ****
if (p.data % 2 == 1) {
// **** q follows p ****
q = p;
p = p.next;
// **** skip this node ****
continue;
}
// **** push even data nodes into stack ****
for (r = p; r != null && (r.data % 2) == 0; r = r.next) {
stack.push(r);
}
// **** reverse nodes in stack ****
while (!stack.isEmpty()) {
// **** ****
p = stack.pop();
// **** ****
p.next = null;
// **** updating the head of the linked list ****
if (q != null)
q.next = p;
else
head = p;
// **** q follows p ****
q = p;
p = p.next;
}
// **** ****
q.next = r;
// **** update pointer ****
p = r;
}
// **** ****
return head;
}
We perform some sanity checks and initialization. We then traverse the linked list.
We skip nodes holding odd integers.
For even nodes, we push them into a stack until an odd integer is encountered.
We reverse the nodes in the stack. The stack only contains nodes with even values. When reversing data it is a good idea to consider the use of a stack.
When done with the stack contents, we continue traversing the linked list.
/**
* Reverse singly linked list.
* Entry point for recursive function reverseRecursive().
*
* !!! NOT PART OF SOLUTION !!!!
*/
static Node reverseList(Node head) {
// **** sanity checks ****
if (head == null || head.next == null)
return head;
// **** initialization ****
h = null;
// **** reverse entire linked list ****
return reverseRecursive(head, null);
}
This is not part of the solution. This is the entry point for reversing the order of all nodes in a linked list. You can go back to the test samples and verify that the output in all cases is as expected.
In this method we initialize the new head of the queue when reversed. The new head is implemented as a static variable outside this function. We could have passed it as an argument. We then call a recursive function. In general I like to name the entry and the recursive methods with the same names. Since I was experimenting I missed such approach.
/**
* Reverse singly linked list.
* Recursive function.
*
* !!! NOT PART OF SOLUTION !!!!
*/
static Node reverseRecursive(Node head, Node prev) {
// **** base case (end of linked list) ****
if (head == null)
return null;
// **** recursive case ****
Node temp = reverseRecursive(head.next, head);
// **** save the new head of the linked list (if needed) ****
if (temp == null) {
// **** new head == last node in the linked list ****
h = head;
}
// **** update the next element ****
head.next = prev;
// **** return new next or the new head ****
return (prev != null) ? prev : h;
}
This is the recursive method. We have a base case that is reached when we are done traversing the linked list and start going back in the call stack. We implement the recursive call. When it returns for the first time we receive a null value. That signals the start (head) of the reversed linked list.
Using the second argument to the method, we can easily reverse the next member in the Node.
Finally we return the head of the reversed linked list or the next element in the reversed list.
If you are having problems with this implementation, I suggest for you to start with a linked list of one element and diagram on paper how the code works. Then increase the number of elements one by one until you get a full understanding of the approach.
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,974 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
Regards;
John
john.canessa@gmail.com