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

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