Sort the linked list in the order of elements appearing in the array | Efficient CPP program to sort given list in order elements are appearing in an array ; Linked list node ; function prototype for printing the list ; Function to insert a node at the beginning of the linked list ; function to print the linked list ; Function that sort list in order of apperaing elements in an array ; Store frequencies of elements in a hash table . ; One by one put elements in lis according to their appearance in array ; Update ' frequency ' nodes with value equal to arr [ i ] ; Modify list data as element appear in an array ; Driver Code ; creating the linked list ; Function call to sort the list in order elements are apperaing in an array ; print the modified linked list
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next ; } ; void printList ( struct Node * ) ; void push ( struct Node * * head_ref , int new_data ) { struct Node * new_node = new Node ; new_node -> data = new_data ; new_node -> next = * head_ref ; * head_ref = new_node ; } void printList ( struct Node * head ) { while ( head != NULL ) { cout << head -> data << " ▁ - > ▁ " ; head = head -> next ; } } void sortlist ( int arr [ ] , int N , struct Node * head ) { unordered_map < int , int > hash ; struct Node * temp = head ; while ( temp ) { hash [ temp -> data ] ++ ; temp = temp -> next ; } temp = head ; for ( int i = 0 ; i < N ; i ++ ) { int frequency = hash [ arr [ i ] ] ; while ( frequency -- ) { temp -> data = arr [ i ] ; temp = temp -> next ; } } } int main ( ) { struct Node * head = NULL ; int arr [ ] = { 5 , 1 , 3 , 2 , 8 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; push ( & head , 3 ) ; push ( & head , 2 ) ; push ( & head , 5 ) ; push ( & head , 8 ) ; push ( & head , 5 ) ; push ( & head , 2 ) ; push ( & head , 1 ) ; sortlist ( arr , N , head ) ; cout << " Sorted ▁ List : " << endl ; printList ( head ) ; return 0 ; }