UPDATE – Added a couple classes and implemented reverse method to reverse the linked list in segments. I will leave this post and move on to a different subject on the next one.
It is a cold Sunday in the Twin Cities of Minneapolis and St. Paul. The forecast called for a winter storm starting last Friday around noon ending Saturday afternoon. The forecast called for 6 to 9 inches of fresh snow and wind blowing up to 45 mph. Due to the forecast, people visiting the area last week or people with plans for the weekend decided to move their schedules and leave the Twin Cities earlier. Airports were crowded and flights were overbooked. When all was said and done, the Twin Cities received about 6 inches of fresh snow. Some places further out received considerable higher amounts (e.g., Hovland, MN 16.5 inches).
Last week I had the opportunity to chat with four technical managers at Microsoft. What a great experience. They all worked on the Azure cloud. It was incredible to feel their enthusiasm on the things they are working on. You hear about companies that promote employees to come up with ideas and see them to fruition. In most cases all that is just lip service. One of the managers came up with an improvement and today is working she is working with her team making it a reality. Hope to see it deployed and operational in the near future.
I would like to cover an approach that should always be considered when one 
is faced with the task of reversing the order of elements in some collection. The collection may or may not be in a specific order. In this case let’s assume the elements are in no specific order.
Before starting this post, I tried to find some code that I wrote and posted of an example on this general subject. I was not able to do so. If I find it in the future, I will update this post with a link to the previous one.
The requirements should be something like: Given this collection (e.g., linked list) reverse the order of each set of n (e.g., n == 3) elements.
In some cases you may get additional requirements (e.g., do not use additional data structures, use minimum amount of memory, etc).
There are many different ways to fulfill the requirements. In my opinion the simplest and most elegant approach is to use a stack. If a stack is not desired due to the additional memory utilization and slightly slower performance, then you can use indices. As usual, some programming languages and the definition of the LinkedList class would reduce memory footprint and perform slightly faster. There are always trade offs when architecting and designing solutions.
9 4 1 2 3 4 5 6 7 8 9 [4, 3, 2, 1, 8, 7, 6, 5, 9] 9 3 1 2 3 4 5 6 7 8 9 [3, 2, 1, 6, 5, 4, 9, 8, 7] 8 3 1 2 3 4 5 6 7 8 [3, 2, 1, 6, 5, 4, 8, 7] 7 3 1 2 3 4 5 6 7 [3, 2, 1, 6, 5, 4, 7] 6 3 1 2 3 4 5 6 [3, 2, 1, 6, 5, 4] 5 3 1 2 3 4 5 [3, 2, 1, 5, 4] 4 3 1 2 3 4 [3, 2, 1, 4] 3 3 1 2 3 [3, 2, 1] 2 3 1 2 [2, 1] 1 3 1 [1]
The Microsoft Visual Studio Code console capture illustrates a set of test cases. Note that I changed the second value once. I did run additional test cases but I believe to have captured enough. Also note that end conditions are tested with the lower test cases.
/*
* Test scaffolding.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read the number of elements to insert in a linked list ****
int n = sc.nextInt();
// **** read the number of elements to reverse at a time ****
int m = sc.nextInt();
// **** read the elements to be inserted in the linked list ****
sc.nextLine();
String str = sc.nextLine();
// **** split values ****
String[] values = str.split(" ");
// *** populate linked list with elements ****
LinkedList<Integer> ll = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
ll.add(Integer.parseInt(values[i]));
}
// **** reverse the elements as needed ****
// ll = reverse(ll, m);
ll = reverseNoStack(ll, m);
// **** display reversed list ****
System.out.println(ll.toString());
// **** close scanner ****
sc.close();
}
}
I wrote the solution using Java. We read the total number of elements for the array. We then read the number of elements that need to be reversed and finally the actual elements. The LinkedList is of type Integer. We could have used other type of generics. For simplicity I left it as Integer.
Note that there are two implementations. One is reverse() and the second reverseNoStack(). I could have executed one after the other but at the time commented one of the lines.
After all is set and done, we display the linked list with the proper reversal of elements, close the scanner and exit.
/*
* Reverse the elements in the list in sets of n NOT using a stack.
*/
static LinkedList<Integer> reverseNoStack(LinkedList<Integer> ll, int n) {
// **** ****
LinkedList<Integer> rll = new LinkedList<Integer>();
// **** traverse the linked list ****
for (int i = 0; i < ll.size(); i += n) { // **** set j **** int j = 0; if (ll.size() - i > n - 1) {
j = n - 1;
} else {
j = ll.size() - i - 1;
}
// **** insert elements into the reverse list ****
for (; j >= 0; j--) {
// **** get element from list ****
int e = ll.get(i + j);
// **** add element to reverse list ****
rll.add(e);
}
}
// **** return list with reversed elements ****
return rll;
}
The approach is quite simple. We create a list that will hold the reversed values. We then traverse the original list and properly set two indices: I and j. We then get elements from the original list and add them to the reversed list. When all is done we return the reversed list.
Note that the code is short but setting up the indices is not as clean and elegant as it could be.
/*
* Reverse the elements in the list in sets of n USING a stack.
*/
static LinkedList<Integer> reverse(LinkedList<Integer> ll, int n) {
// **** list with reversed elements ****
LinkedList<Integer> rll = new LinkedList<Integer>();
// **** used to reverse entries ****
Stack<Integer> stack = new Stack<Integer>();
// **** iterate through the linked list ****
Iterator<Integer> it = ll.iterator();
while (it.hasNext()) {
// **** collect the elements to be reversed ****
for (int i = 0; (i < n) && it.hasNext(); i++) {
stack.push(it.next());
}
// **** pop elements inserting them into the temporary list ****
while (!stack.empty()) {
rll.add(stack.pop());
}
}
// **** return list with reversed elements ****
return rll;
}
This is similar to the previous function but we use a stack. When problems call for reversing orders the Stack class should be considered. I implemented the reverseNoStack() function just to comply with not using an additional data structure.
The core of the approach is to take n elements at a time and push them into a stack. We then simply pop the elements reversing their order and adding them to the new reversed list (rll). When done we return rll.
I was going to implement a solution using C/C++ using a library that I created some time ago which is in production. Such implementation uses doubly linked lists so it is very simple to get the desired results without the use of additional memory or overhead.
I was also going to implement the reversal using a recursive call and no stack. Such approach would be less efficient and harder to follow and maintain. The reason is that we would not have used a stack, the indexing complexity would be there and recursive calls make use of stack and depending on the number of calls can cause stack overflow exceptions.
I went back to the code with the intention of implementing the reversal using and not using a stack with custom classes (e.g., LLNode and LL). Have to take care of work so I only implemented the method to reverse the linked list using a stack.
/*
* Linked list node.
*/
class LLNode {
// **** ****
int value;
LLNode next;
// **** constructor ****
public LLNode(int value) {
this.value = value;
this.next = null;
}
// **** toString ****
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("value: " + value);
return sb.toString();
}
}
This class is used to implement the nodes in our new linked list. It has a constructor and a toString() method. I am not sure if I used the toString() method in the code.
/*
* Linked list.
*/
class LL {
// **** ****
public LLNode head;
public LLNode tail;
// **** ****
static LL linkedList = null;
// **** constructor ****
public LL() {
this.head = null;
this.tail = null;
}
// **** add ****
public void add(int value) {
// **** ****
LLNode node = new LLNode(value);
// **** check if list is empty ****
if (this.head == null && this.tail == null) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
}
// **** toString ****
public String toString() {
// **** open list ****
StringBuilder sb = new StringBuilder("[");
// **** traverse linked list ****
for (LLNode p = this.head; p != null; p = p.next) {
if (p.next == null) {
sb.append(p.value);
} else {
sb.append(p.value + ", ");
}
}
// **** close list ****
sb.append("]");
// **** return string representation ****
return sb.toString();
}
// **** reverse with stack ****
public LL reverse(LL ll, int m) {
// **** reversed linked list to return to caller ****
LL rll = new LL();
// **** to reverse set of elements ****
Stack<Integer> stack = new Stack<Integer>();
// **** traverse the linked list ****
LLNode p = ll.head;
while (p != null) {
// **** push elements into stack ****
for (int i = 0; (i < m) && (p != null); i++, p = p.next) {
stack.push(p.value);
}
// **** pop elements from stack and insert them into the reversed list ****
while (!stack.isEmpty()) {
rll.add(stack.pop());
}
}
// **** return list with reversed elements ****
return rll;
}
}
The LL class implements a single list linked list using the LLNode class. We have a constructor, an add() method to add elements into the linked list, a toString() method to display the list (which I use) and finally the reverse() method that reverses the linked list.
/*
* Test scaffolding.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read the number of elements to insert in a linked list ****
int n = sc.nextInt();
// **** read the number of elements to reverse at a time ****
int m = sc.nextInt();
// **** read the elements to be inserted in the linked list ****
sc.nextLine();
String str = sc.nextLine();
// **** split values ****
String[] values = str.split(" ");
// *** populate linked list(s) ****
LinkedList<Integer> ll = new LinkedList<Integer>();
LL myll = new LL();
for (int i = 0; i < n; i++) {
ll.add(Integer.parseInt(values[i]));
myll.add(Integer.parseInt(values[i]));
}
// **** reverse the elements in the linked list as needed ****
// ll = reverse(ll, m);
// ll = reverseNoStack(ll, m);
myll = myll.reverse(myll, m);
// **** display reversed list ****
// System.out.println(ll.toString());
System.out.println(myll.toString());
// **** close scanner ****
sc.close();
}
In the main() function we declare and populate a new linked list using the LL class. We then reverse the elements and display results.
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 serve of assistance 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 message using the following address: john.canessa@gmail.com. All messages will remain private.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
John
Twitter: @john_canessa