Home » 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.


Time complexity : O(n)


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
            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
//display linked list
void display(struct LLNode**node)
    struct LLNode *temp= *node;
            temp=temp->next; //move to next node
        //O(number of nodes)

void ReverseLL(LLNode *&head)
    struct LLNode* prev = NULL, *curr = head, *next;
        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);
        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;
        ascending->next = curr;
        ascending = ascending->next;
        curr = curr->next;
            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);

    *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: ";
    cout<<"\nOutput linked list is: ";
    return 0;

READ  Detect a loop in the Linked List


How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions