Iterative selection sort for linked list | C ++ implementation of the approach ; Linked List Node ; Utility function to create a new Linked List Node ; Function to sort a linked list using selection sort algorithm by swapping the next pointers ; While b is not the last node ; While d is pointing to a valid node ; If d appears immediately after b ; Case 1 : b is the head of the linked list ; Move d before b ; Swap b and d pointers ; Update the head ; Skip to the next element as it is already in order ; Case 2 : b is not the head of the linked list ; Move d before b ; Swap b and d pointers ; Skip to the next element as it is already in order ; If b and d have some non - zero number of nodes in between them ; Case 3 : b is the head of the linked list ; Swap b -> next and d -> next ; Swap b and d pointers ; Skip to the next element as it is already in order ; Update the head ; Case 4 : b is not the head of the linked list ; Swap b -> next and d -> next ; Swap b and d pointers ; Skip to the next element as it is already in order ; Update c and skip to the next element as it is already in order ; Function to print the list ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * next ; } ; Node * newNode ( int val ) { Node * temp = new Node ; temp -> data = val ; temp -> next = NULL ; return temp ; } Node * selectionSort ( Node * head ) { Node * a , * b , * c , * d , * r ; a = b = head ; while ( b -> next ) { c = d = b -> next ; while ( d ) { if ( b -> data > d -> data ) { if ( b -> next == d ) { if ( b == head ) { b -> next = d -> next ; d -> next = b ; r = b ; b = d ; d = r ; c = d ; head = b ; d = d -> next ; } else { b -> next = d -> next ; d -> next = b ; a -> next = d ; r = b ; b = d ; d = r ; c = d ; d = d -> next ; } } else { if ( b == head ) { r = b -> next ; b -> next = d -> next ; d -> next = r ; c -> next = b ; r = b ; b = d ; d = r ; c = d ; d = d -> next ; head = b ; } else { r = b -> next ; b -> next = d -> next ; d -> next = r ; c -> next = b ; a -> next = d ; r = b ; b = d ; d = r ; c = d ; d = d -> next ; } } } else { c = d ; d = d -> next ; } } a = b ; b = b -> next ; } return head ; } void printList ( Node * head ) { while ( head ) { cout << head -> data << " ▁ " ; head = head -> next ; } } int main ( ) { Node * head = newNode ( 5 ) ; head -> next = newNode ( 4 ) ; head -> next -> next = newNode ( 3 ) ; head = selectionSort ( head ) ; printList ( head ) ; return 0 ; }