Introduction
The LinkedList data structure is an extremely powerful data structure with a wide range of applications. LinkedList is the source of many of the questions asked in most companies. As a result, having a thorough understanding of this data structure is important.
In this blog, we will discuss a question related to LinkedList and will discuss two different approaches that can be used to solve the problem.
Problem Statement
Rearrange a list of numbers in such a way that the minimum and maximum numbers alternate. The first and second components of the list should be the smallest and largest respectively of all the entries in the list. It is not allowed to use extra space.
Sample Example 1
Input
Output
Explanation: The minimum element in the list is 1 so it appears at the starting position. After that the maximum element appears then the 2nd minimum element and 2nd maximum element appears. This continues till we reach the end of the list.
Sample Example 2
Input
Output
Approach
The idea is to sort the given list and then select the first and the last element of the list and keep inserting them inside the new resultant list.
Algorithm
-
Sort the given list.
-
Create two variables that will point to the first and the last element of the list.
-
Push the first and last element into the new resultant list.
-
Increment the variable that points to the first element so that it points to the second element.
-
Decrement the variable that points to the last element so that it points to the second last element of the list.
-
Keep repeating from point 3 to point 5 till the first and the last variable point to the same element or the size of the resultant list becomes the same as the original list.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
void rearrangeElements(list<int> &input){
// sorting the list in ascending order
input.sort();
// creating new list to store the result
list<int> result;
// iterator pointing to the first element
list<int>::iterator starting = input.begin();
// iterator pointing to the last element of the list
list<int>::iterator ending = input.end();
ending--;
// Loop to insert element inside our resultant list
while(result.size() != input.size()){
// inserting the minimum element
result.push_back(*starting);
// if both starting and ending iterator
// points at the same location we'll break out of the loop
if(starting == ending) break;
// inserting the maximum element
result.push_back(*ending);
// incrementing the starting iterator
// so that it points to next minimum element
starting++;
// decrementing the ending iterator
// so that it points to the next maximum element
ending--;
}
// printing the list
cout<<”Linked list: “;
for(auto it : result){
cout << it << “->”;
}
cout << “NULL” << endl;
}
int main() {
// input list
list<int> input({ 9, 8, 3, 5, 6, 1 });
// calling the rearrange function
rearrangeElements(input);
return 0;
}
Output
Linked list: 1->9->3->8->5->6->NULL
Time Complexity
The sorting algorithm requires O(nlogn) time and our loop requires O(n) time complexity. So the overall complexity of our algorithm is O(nlogn) + O(n) = O(nlogn).
Space Complexity
As we are saving the elements in the resultant list so the space complexity of our algorithm is O(n).