# Sort list whose alternate nodes are in ascending and descending order without using sorting techniques

### Problem statement to sort list whose alternate nodes are in ascending and descending order:

Given is a singly linked list whose alternate nodes are sorted in ascending and descending order i.e. nodes at odd positions form an ascending ordered linked list and nodes at even positions form a descending ordered linked list. You have to sort this entire list in ascending order **without using any sorting technique.**

### Sort list whose alternate nodes are in ascending and descending order Example:

Consider a singly linked list whose alternate nodes are in ascending and descending order 1-> 45-> 8 -> 23-> 19-> 11-> 34-> 5-> 67-> NULL Resultant list after sorting 1-> 5-> 8-> 11-> 19-> 23-> 34-> 45-> 67-> NULL

### Algorithm to sort list whose alternate nodes are in ascending and descending order **without using any sorting technique:**

- Seperate the list into two lists which are in ascending and descending order respectively.
- Reverse the list which is in descending order.
- Merge this list with the ascending ordered list.

### Solution code in C++ to sort list whose alternate nodes are in ascending and descending order without using any sorting technique:

#include <bits/stdc++.h> using namespace std; /*Standard structure that defines the node*/ struct node { int data; node * next; }; /*Function inserts nodes at end of Linked List*/ void Insert(node **head, node **last, int data) { node *temp = new node; temp->data = data; temp->next = NULL; /*If list is empty.*/ if(*head == NULL) { /*The first node is the head and last node*/ *head = temp; *last = temp; } else { (*last)->next = temp; *last = temp; } } /*Function reverses list*/ void Reverse(node **head) { node *prev = NULL; node *curr = *head; node *next = NULL; while(curr) { next = curr->next; curr->next = prev; prev = curr; curr = next; } *head = prev; } /*Function applies sorted merge on the lists and returns head pointer of sorted list.*/ node* Merge(node *desc_list, node *asc_list) { /*Pointers to final sorted list*/ node *sorted_list = NULL; node *last = NULL; /*Loop to traverse both lists simultaneously and insert smaller node into sorted list*/ while(desc_list != NULL && asc_list != NULL) { if(asc_list->data < desc_list->data) { Insert(&sorted_list,&last,asc_list->data); asc_list = asc_list->next; } else if(desc_list->data < asc_list->data) { Insert(&sorted_list,&last,desc_list->data); desc_list = desc_list->next; } else { Insert(&sorted_list,&last,asc_list->data); Insert(&sorted_list,&last,desc_list->data); asc_list = asc_list->next; desc_list = desc_list->next; } } /*If number of nodes in asc_list are less than that in desc_list*/ while(desc_list != NULL) { Insert(&sorted_list,&last,desc_list->data); desc_list = desc_list->next; } /*If number of nodes in desc_list are less than that in asc_list*/ while(asc_list != NULL) { Insert(&sorted_list,&last,asc_list->data); asc_list = asc_list->next; } /*Returns head pointer of sorted list*/ return sorted_list; } /*Function to sort linked list in ascending order*/ void Sort(node **head) { /*Initialising pointers of ascending list*/ node *asc_head = NULL; node *asc_tail = NULL; /*Initialising pointers of descending list*/ node *desc_head = NULL; node *desc_tail = NULL; node *curr = *head; int i = 1; /*Loop traverses and splits given list*/ while(curr != NULL) { /*Nodes at odd positions inserted in asc_list*/ if(i % 2 != 0) Insert(&asc_head, &asc_tail, curr->data); /*Nodes at even positions inserted in desc_list*/ else Insert(&desc_head, &desc_tail, curr->data); i++; curr = curr->next; } /*Call function to reverse desc_list*/ Reverse(&desc_head); /*Call function to merge the two lists*/ *head = Merge(desc_head, asc_head); } /*Function that is used to print the Linked List*/ void printList(node *head) { while (head != NULL) { cout<<head->data<<"-> "; head = head->next; } cout<<"NULL"; } /* Driver program to test above functions*/ int main() { /*initialising head and last pointers to list*/ node* head = NULL; node* last = NULL; /*Inserts nodes at end of list*/ Insert(&head, &last, 1); Insert(&head, &last, 45); Insert(&head, &last, 8); Insert(&head, &last, 23); Insert(&head, &last, 19); Insert(&head, &last, 11); Insert(&head, &last, 34); Insert(&head, &last, 1); Insert(&head, &last, 67); cout<<"Created Linked list is:\n"; printList(head); /*Calling sort function*/ Sort(&head); cout<<"\nResultant Linked list is:\n"; printList(head); return 0; }

**Output:**

Created Linked list is: 1-> 45-> 8-> 23-> 19-> 11-> 34-> 1-> 67-> NULL Resultant Linked list is: 1-> 1-> 8-> 11-> 19-> 23-> 34-> 45-> 67-> NULL

**Time complexity** to perform this sort list without using any sorting technique:** O(N)
**where N is the number of nodes in the given linked list.