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

Saksham Gupta
Last Updated: May 13, 2022

Introduction

Just as every dish is incomplete without salt, every tech interview is incomplete without Linked List. 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 alternating ascending and descending order.

Problem Statement

We have been given a linked list which is sorted 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.

 

 

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.

 

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 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;
}

Input

2 38 3 28 8

Output

2 3 8 28 38

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.

Key Takeaways

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. But don't worry, we have a solution for that too. Move over to our industry-leading practice platform CodeStudio to practice top problems. Till then, Happy Coding!

Was this article helpful ?
0 upvotes