Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example 1
1.3.
Sample Example 2
2.
Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Optimized Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Frequently Asked Questions
4.1.
What are the four types of linked list?
4.2.
What is the difference between array and linked list?
4.3.
Which sorting algorithms can be used to sort a random linked list with minimum time complexity?
5.
Conclusion
Last Updated: Mar 27, 2024

Rearrange a Linked List such that it contains alternating Minimum and Maximum elements

Author Harsh
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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

  1. Sort the given list.
     
  2. Create two variables that will point to the first and the last element of the list.
     
  3. Push the first and last element into the new resultant list.
     
  4. Increment the variable that points to the first element so that it points to the second element.
     
  5. Decrement the variable that points to the last element so that it points to the second last element of the list.
     
  6. 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;
}
You can also try this code with Online C++ Compiler
Run Code

 

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).

Optimized Approach

We can optimize the space complexity of the above algorithm by tweaking the algorithm a little.

Algorithm

  1. Sort the given list in ascending order.
     
  2. Declare an iterator that points to the first element then increment it by one position.
     
  3. Pop the last element from the list and insert it in the correct position.
     
  4. increment the iterator by one position.
     
  5. Keep repeating step 3 and 4 until the half of the list is traversed.
     

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

void rearrangeElementsOptimized(list<int>& input) {
    // sort the list in ascending order
    input.sort();
 
    // get iterator to first element of the list
    list<int>::iterator itr = input.begin();

	// incrementing the iterator by one position
	// to get the location where we need to insert the
	// maximum element
    itr++;

	for (int i = 1; i < (input.size() + 1)/2; i++){
		// getting the value of th last element (maximum)
		int maxElement = input.back();


		// removing the last element from the list
		input.pop_back();


		// inserting the maximum element after minimum element
		input.insert(itr, maxElement);


		// incrementing the iterator to get the next
		// location where we need to insert next maximum element
		itr++;
	}
 	
	// printing the list
	cout<<”Linked list: “;
	for (auto it : input) {
		cout << it << “->”;
	}
	cout << “NULL” << endl;

}


int main() {

// input list
list<int> input({ 1,  5,  2,  7,  9 });

// calling the rearrange function
rearrangeElementsOptimized(input);

return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output

Linked list: 1->9->2->7->5->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 not using any extra space so the space complexity is O(1).

Also see,  Rabin Karp Algorithm

Frequently Asked Questions

What are the four types of linked list?

There are four key types of linked lists are Singly linked lists, Doubly linked lists, Circular linked lists, and Circular doubly linked lists.
 

What is the difference between array and linked list?

An array is a collection of elements with the same data type. whereas linked list is an ordered collection of elements of the same type with pointers connecting each element to the next. The array index can be used to retrieve array elements at random. In linked lists, random access is not possible.
 

Which sorting algorithms can be used to sort a random linked list with minimum time complexity?

For linked lists, both Merge sort and Insertion sort can be used.
 

Conclusion

In this article, we have discussed a question related to LinkedList using two different approaches. We hope that this blog has enhanced your knowledge and cleared all of your doubts regarding the above question. Want to learn more?, check out our articles like Insert a node at a specific position in a linked listDeletion of a linked listApplication of Linked List, Is it possible to reverse a linked list in less than O(n)?, and many more on our Website

Recommended Problems -

You can also visit Guided Path on Coding Ninjas Studio to upskill yourself in Competitive ProgrammingData Structures and AlgorithmsSystem DesignJavaScript, and many more! Check out the mock test series and participate in the contests hosted on Coding Ninjas Studio to test your proficiency in coding. But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, etc; you must look at the interview experiences, problems, and interview bundle for placement preparations.

Nevertheless, you can also consider our paid courses to give your career an edge over others!

Do upvote the blogs if you find it helpful and engaging!

Happy Learning!

Live masterclass