Home » Technical Interview Questions » LinkedList Interview Questions » Sort a linked list that is sorted alternating ascending and descending

# Sort a linked list that is sorted alternating ascending and descending

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

//O(1) constant time
}

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

{
struct LLNode* prev = NULL, *curr = head, *next;
while(curr)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
//O(number of nodes)
}

// A utility function to merge two sorted linked lists
{

{
}
{
}
struct LLNode *temp = NULL;
{
}
else
{
}
return temp;
}
//Split function
{

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
}
//function to sort
{
//Split into 2 listss

}

//Main function
int main()
{