1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Code
3.2.
Complexities
4.
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

Saksham Gupta
0 upvote

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

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 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 *newNode = new Node(data);

// In this case the new node will become head of the list.
{
}
else
{
}
}

{
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
}

// Function to reverse the Linked List.
{
Node *prev = NULL;
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)
{
*top1 = insert(*top1, 0);
*top2 = insert(*top2, 0);

// '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.
{
// '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.

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

// Merging both the lists.
}

// Main function
int main()
{
// Creating linked list: 2->38->3->28->8 by inserting nodes at the beginning one by one.

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

// Printing the final sorted list.

return 0;
}``````

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.

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