Recursive selection sort for singly linked list | Swapping node links | 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 code ; create linked list 10.12 .8 .4 .6 ; sort the linked list
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def swapNodes ( head_ref , currX , currY , prevY ) : NEW_LINE INDENT head_ref = currY NEW_LINE prevY . next = currX NEW_LINE temp = currY . next NEW_LINE currY . next = currX . next NEW_LINE currX . next = temp NEW_LINE return head_ref NEW_LINE DEDENT def recurSelectionSort ( head ) : NEW_LINE INDENT if ( head . next == None ) : NEW_LINE INDENT return head NEW_LINE DEDENT min = head NEW_LINE beforeMin = None NEW_LINE ptr = head NEW_LINE while ( ptr . next != None ) : NEW_LINE INDENT if ( ptr . next . data < min . data ) : NEW_LINE INDENT min = ptr . next NEW_LINE beforeMin = ptr NEW_LINE DEDENT ptr = ptr . next NEW_LINE DEDENT if ( min != head ) : NEW_LINE INDENT head = swapNodes ( head , head , min , beforeMin ) NEW_LINE DEDENT head . next = recurSelectionSort ( head . next ) NEW_LINE return head NEW_LINE DEDENT def sort ( head_ref ) : NEW_LINE INDENT if ( ( head_ref ) == None ) : NEW_LINE INDENT return None NEW_LINE DEDENT head_ref = recurSelectionSort ( head_ref ) NEW_LINE return head_ref NEW_LINE DEDENT def push ( head_ref , new_data ) : NEW_LINE INDENT new_node = Node ( 0 ) NEW_LINE new_node . data = new_data NEW_LINE new_node . next = ( head_ref ) NEW_LINE ( head_ref ) = new_node NEW_LINE return head_ref NEW_LINE DEDENT def printList ( head ) : NEW_LINE INDENT while ( head != None ) : NEW_LINE INDENT print ( head . data , end = " ▁ " ) NEW_LINE head = head . next NEW_LINE DEDENT DEDENT head = None NEW_LINE head = push ( head , 6 ) NEW_LINE head = push ( head , 4 ) NEW_LINE head = push ( head , 8 ) NEW_LINE head = push ( head , 12 ) NEW_LINE head = push ( head , 10 ) NEW_LINE print ( " Linked ▁ list ▁ before ▁ sorting : " ) NEW_LINE printList ( head ) NEW_LINE head = sort ( head ) NEW_LINE print (   " Linked list after sorting : " ) NEW_LINE printList ( head ) NEW_LINE