Data structure - How would you sort a linked list?

How would you sort a linked list?

Single linked list- Here, the pointer can only move in one direction.

Double linked list- Here, the pointer can move in forward or backward direction.

Circular linked list- Here, the address of the last node points to the first node of the list so as to make it a circular linked list

How would you sort a linked list?

Step 1: Compare the current node in the unsorted list with every element in the rest of the list. If the current element is more than any other element go to step 2 otherwise go to step 3.

Step 2: Position the element with higher value after the position of the current element. Compare the next element. Go to step1 if an element exists, else stop the process.

Step 3: If the list is already in sorted order, insert the current node at the end of the list. Compare the next element, if any and go to step 1 or quit.