How do we sort a linked list?

In this post, we see one such method using bubble sort algorithm.

In this post, we see one such method using bubble sort algorithm.

We have discussed the Bubble sort algorithm on arrays in my previous post. The same algorithm is also applicable to singly linked lists as well.

We first find the length of the linked list (len). The outer loop iterates for (len-1) times and the inner loop iterates for (len-1-i) times.

Since we cannot access the linked list elements by their indices, we use two pointers to keep track of the current node and the next node which will be compared and swapped in each iteration.

Here is the Object Oriented C++ implementation.