Simple Insertion sort is easily adaptable to singly linked list. In this method there is an array link of pointers, one for each of the original array elements. Initially link[i] = i + 1 for 0 < = I < n-1 and link [n-1] = -1. Thus the array can be thought of as a linear link list pointed to by an external pointer first initialized to 0. To insert the kth element the linked list is traversed until the proper position for x[k] is found, or until the end of the list is reached. At that point x[k] can be inserted into the list by merely adjusting the list pointers without shifting any elements in the array. This reduces the time required for insertion but not the time required for searching for the proper position. The number of replacements in the link array is O (n).
Each node from the unsorted linked list is to be detached one by one from the front and attached to the new list pointed by s head. While attaching, the value got stored in each node is considered so that it is inserted at the proper position.