Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Code
3.2.
Complexities
4.
Frequently Asked Questions(FAQs)
4.1.
What is the time complexity of running Merge Sort on Linked List?
4.2.
Which Sorting algorithm is most suited for large data sets?
4.3.
Can we access the nodes of Linked Lists randomly by using indices like in an array?
5.
Conclusion
Last Updated: Mar 27, 2024

Sort a Linked List that is Sorted Alternating Ascending and Descending Orders

Author Saksham Gupta
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Linked List

Introduction

Just as every dish is incomplete without salt, every tech interview is incomplete without Linked List Data Structure. There is hardly any instance when the interviewee isn’t asked about this favorite topic of interviewers. Thus practicing the questions on Linked List will surely give you an upper hand. Today we will see one such question which is regularly asked in interviews, i.e., sort a linked list that is sorted in alternating ascending and descending order.

Recommended Topic, Floyds Algorithm

Problem Statement

We have been given a linked list which is sorted in alternating ascending and descending order, and our task is to return the linked list in ascending order.

Let’s say the linked List that is given to us is.

 

Linked List

 

Thus if we see the alternate places, we can see that list 2->3->8 is sorted in ascending order and 38->28 is sorted in descending order. We have to return the list in ascending order which will look something like this.

 

Linked List

This is the sorted list and our final answer.

You must be thinking that we can simply apply any sorting algorithm, preferably merge sort and get the final sorted list. 

Yes, you are right, but then how are we using the condition that is given to us in the question that the linked List is sorted in alternating ascending and descending orders?

Approach

We will break the linked list into two parts, one for the ascending part and the second for the descending part (we can do that easily as we only have to pick the alternate elements). Then we will reverse the descending part, and we’ll get two linked lists that are sorted in ascending order. Now, all we have to do is to merge these two sorted lists, and we will get the desired sorted list. You can refer here on how to merge the two sorted lists. Let’s see the code to get a better understanding of the approach.

Code

#include <iostream>
using namespace std;

class Node
{
public:
   int data;
   Node *next;
   Node(int data)
   {
       this->data = data;
       this->next = NULL;
   }
};

// Function to insert a node at the beginning of the linked list.
Node *insert(Node *head, int data)
{
   Node *newNode = new Node(data);

   // In this case the new node will become head of the list.
   if (head == NULL)
   {
       head = newNode;
   }
   else
   {
       newNode->next = head;
       head = newNode;
   }
   return head;
}

// Printing the linked list.
void print(Node *head)
{
   Node *temp = head;
   while (temp != NULL)
   {
       cout << temp->data << " ";
       temp = temp->next;
   }
}

// Function to reverse the Linked List.
Node *reverseLL(Node *head)
{
   Node *prev = NULL;
   Node *curr = head;
   Node *next;
   while (curr != NULL)
   {
       next = curr->next;
       curr->next = prev;
       prev = curr;
       curr = next;
   }
   return prev;
}

// Function to merge two sorted linked lists.
Node *mergeBothLists(Node *top1, Node *top2)
{
   if (top2 == NULL)
   {
       return top1;
   }
   if (top1 == NULL)
   {
       return top2;
   }

   Node *temp = NULL;

   // Regular merging function concept.
   if (top1->data >= top2->data)
   {
       temp = top2;
       top2->next = mergeBothLists(top1, top2->next);
   }
   else
   {
       temp = top1;
       top1->next = mergeBothLists(top1->next, top2);
   }
   return temp;
}

// Split function.
void splitLL(Node *head, Node **top1, Node **top2)
{
   //Initialize with zero heads.
   *top1 = insert(*top1, 0);
   *top2 = insert(*top2, 0);

   Node *temp = head;

   // 'TOP1' is holding an ascending ordered list.
   Node *firstPart = *top1;

   // 'TOP2' is holding a descending ordered list.
   Node *secondPart = *top2;

   while (temp != NULL)
   {
       // As 'FIRST_PART' is holding an ascending ordered list, we first add an element to it.
       firstPart->next = temp;
       firstPart = firstPart->next;
       temp = temp->next;

       // If the 'TEMP' is still not NULL then that particular element would be added in 'SECOND_PART' list.
       if (temp != NULL)
       {
           secondPart->next = temp;
           secondPart = secondPart->next;
           temp = temp->next;
       }
   }

   // Setting tails to NULL.
   firstPart->next = NULL;
   secondPart->next = NULL;

   // Remove zeros that were inserted initially.
   *top2 = (*top2)->next;
   *top1 = (*top1)->next;
}

// Function going to sort the List.
Node* sortLL(Node* head)
{
   // 'FIRST_PART' will store an ascending ordered list while 'SECOND_PART' will store the descending ordered list.
   Node *firstPart, *secondPart;

   // Split the list into 2 parts.
   splitLL(head, &firstPart, &secondPart);

   // Reversing the descending ordered list.
   secondPart = reverseLL(secondPart);

   // Merging both the lists.
   head = mergeBothLists(firstPart, secondPart);
}

// Main function
int main()
{
   // Creating linked list: 2->38->3->28->8 by inserting nodes at the beginning one by one.
   Node *head = NULL;
   head = insert(head, 8);
   head = insert(head, 28);
   head = insert(head, 3);
   head = insert(head, 38);
   head = insert(head, 2);

   // Calling the 'sortLL()' function to sort the list.
   head = sortLL(head);

   // Printing the final sorted list.
   print(head);

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

Input

2 38 3 28 8

Output

2 3 8 28 38

Complexities

Time Complexity

O(L), where ‘L’ represents the length of the linked list.

As we are traversing the linked list only once it will cost us O(L) time. Similarly for merging also it will take O(L). Hence the time complexity is O(L) + O(L) ~ O(L).

Space Complexity

O(1).

As no extra space is used the space complexity is constant.

Frequently Asked Questions(FAQs)

What is the time complexity of running Merge Sort on Linked List?

The time complexity is O(NlogN) where N is the length of the Linked List

Which Sorting algorithm is most suited for large data sets?

Merge Sort is most suited for large data sets as it has a worst-case time complexity of O(NlogN) and is stable in nature

Can we access the nodes of Linked Lists randomly by using indices like in an array?

No. To access any node of a Linked List we have to access its previous node.

Conclusion

We saw how we could sort a linked list that is sorted in alternating ascending and descending orders. We saw how we could avoid direct merge sort and make use of the condition that is given to us. Now, after learning this new problem, you might be getting the impression that Linked Lists is a simple topic, and you are well on your way to mastering it. But there is still a long way to go. 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

To study more about Linked Lists, refer to Applications Of Linked Lists.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Live masterclass