Recursive selection sort for singly linked list | Swapping node links | C ++ implementation of recursive selection sort for singly linked list | Swapping node links ; A Linked list node ; function to swap nodes ' currX ' and ' currY ' in a linked list without swapping data ; make ' currY ' as new head ; adjust links ; Swap next pointers ; function to sort the linked list using recursive selection sort technique ; if there is only a single node ; ' min ' - pointer to store the node having minimum data value ; ' beforeMin ' - pointer to store node previous to ' min ' node ; traverse the list till the last node ; if true , then update ' min ' and ' beforeMin ' ; if ' min ' and ' head ' are not same , swap the head node with the ' min ' node ; recursively sort the remaining list ; function to sort the given linked list ; if list is empty ; sort the list using recursive selection sort technique ; function to insert a node at the beginning of the linked list ; allocate node ; put in the data ; link the old list to the new node ; move the head to point to the new node ; function to print the linked list ; Driver program to test above ; create linked list 10 -> 12 -> 8 -> 4 -> 6 ; sort the linked list
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next ; } ; void swapNodes ( struct Node * * head_ref , struct Node * currX , struct Node * currY , struct Node * prevY ) { * head_ref = currY ; prevY -> next = currX ; struct Node * temp = currY -> next ; currY -> next = currX -> next ; currX -> next = temp ; } struct Node * recurSelectionSort ( struct Node * head ) { if ( head -> next == NULL ) return head ; struct Node * min = head ; struct Node * beforeMin = NULL ; struct Node * ptr ; for ( ptr = head ; ptr -> next != NULL ; ptr = ptr -> next ) { if ( ptr -> next -> data < min -> data ) { min = ptr -> next ; beforeMin = ptr ; } } if ( min != head ) swapNodes ( & head , head , min , beforeMin ) ; head -> next = recurSelectionSort ( head -> next ) ; return head ; } void sort ( struct Node * * head_ref ) { if ( ( * head_ref ) == NULL ) return ; * head_ref = recurSelectionSort ( * head_ref ) ; } void push ( struct Node * * head_ref , int new_data ) { struct Node * new_node = ( struct Node * ) malloc ( sizeof ( struct 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 ; } } int main ( ) { struct Node * head = NULL ; push ( & head , 6 ) ; push ( & head , 4 ) ; push ( & head , 8 ) ; push ( & head , 12 ) ; push ( & head , 10 ) ; cout << " Linked ▁ list ▁ before ▁ sorting : n " ; printList ( head ) ; sort ( & head ) ; cout << " Linked list after sorting : n " ; printList ( head ) ; return 0 ; }