Rearrange linked list in increasing order (Sort linked list)

Given a linked list, write a function to rearrange its nodes so they are sorted in increasing order. In other words, sort linked list.


We can use SortedInsert() function to sort linked list. We start with an empty result list. Iterate through the source list and SortedInsert() each of its nodes into the result list. Be careful to note the .next field in each node before moving it into the result list.


Download   Run Code


2 -> 3 -> 4 -> 6 -> 8 -> 9 -> null


Download   Run Code


2 -> 3 -> 4 -> 6 -> 8 -> 9 -> null

The time complexity of above solution is O(n2). Please see Merge Sort Algorithm for Singly Linked List for sorting the linked list in O(nlog(n)) time.


1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

I guess it’s more natural to sort a linked list using merge sort in O(n*log(n)) time with O(1) auxiliary space rather than using quadratic selection sort.