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.

C

Download   Run Code

Output:

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

Java

Download   Run Code

Output:

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.

 
Source: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
yndi
Guest

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.