## In the given linked list, the list is in alternating ascending and descending orders. We need to write an efficient solution to sort the list.

### Example

**Time complexity : O(n)**

## Algorithm

**a.** We need to separate linked list into two separate linked lists, one linked list contains odd position elements and another with even.

**b.** We reverse the list with descending order. (use reverse function)

**c.** We merge both lists.

** 1.** Compare the heads of the ascending and descending.

** 2.** We replace the head of input with greater head of both lists and move the head position in input LL and in number added.

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
struct LLNode
{
int data;
struct LLNode *next;
};
/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
struct LLNode* curr = new LLNode;
curr->data = dataToBeInserted;
curr->next = NULL;
if(*head == NULL)
*head=curr; //if this is first node make this as head of list
else
{
curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
*head=curr;
}
//O(1) constant time
}
//display linked list
void display(struct LLNode**node)
{
struct LLNode *temp= *node;
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<"->";
else
cout<<temp->data;
temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}
void ReverseLL(LLNode *&head)
{
struct LLNode* prev = NULL, *curr = head, *next;
while(curr)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
//O(number of nodes)
head = prev;
}
// A utility function to merge two sorted linked lists
struct LLNode *MergeLL(struct LLNode *head1,struct LLNode *head2)
{
if(head1 == NULL)
{
return head2;
}
if(head2 == NULL)
{
return head1;
}
struct LLNode *temp = NULL;
if (head1->data < head2->data)
{
temp = head1;
head1->next = MergeLL(head1->next, head2);
}
else
{
temp = head2;
head2->next = MergeLL(head1, head2->next);
}
return temp;
}
//Split function
void Split(struct LLNode *head,struct LLNode **head1,struct LLNode **head2)
{
//Initialize with zero heads
insertAtBeginning(&*head1, 0);
insertAtBeginning(&*head2, 0);
struct LLNode *ascending = *head1;//head1 with ascending list
struct LLNode *descending = *head2;//head2 with descending list
struct LLNode *curr = head;
while(curr)
{
ascending->next = curr;
ascending = ascending->next;
curr = curr->next;
if(curr)
{
descending->next = curr;
descending = descending->next;
curr = curr->next;
}
}
ascending->next = NULL;
descending->next = NULL;
//Remove zeroes
*head1 = (*head1)->next;
*head2 = (*head2)->next;
}
//function to sort
void Sort(struct LLNode **head)
{
struct LLNode *headAscn , *headDscn;
//Split into 2 listss
Split(*head, &headAscn, &headDscn);
ReverseLL(headDscn);
*head = MergeLL(headAscn, headDscn);
}
//Main function
int main()
{
struct LLNode *head = NULL;
insertAtBeginning(&head, 20);
insertAtBeginning(&head, 50);
insertAtBeginning(&head, 40);
insertAtBeginning(&head, 30);
insertAtBeginning(&head, 60);
insertAtBeginning(&head, 10);
cout<<"Input linked list is: ";
display(&head);
Sort(&head);
cout<<"\nOutput linked list is: ";
display(&head);
return 0;
}
```

Try It

**Next >**
**< Prev**