DIR Return Create A Forum - Home
---------------------------------------------------------
techsuns
HTML https://techsuns.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Puzzles && Algorithms
*****************************************************
#Post#: 440--------------------------------------------------
linked list sort
By: dinesh Date: February 5, 2013, 11:08 pm
---------------------------------------------------------
Give most efficient solution O(n) time complexity O(1) space:
Given a linked list of 0s, 1s and 2s, sort it.
#Post#: 441--------------------------------------------------
Re: linked list sort
By: kranthipls Date: February 5, 2013, 11:35 pm
---------------------------------------------------------
Declare three counters temp0, temp1, temp2;
Now parse through the list and update these counters;
After the first parsing we have number of 0s,1s and 2s in the
list.
Now from starting with head node of the list fill it first with
0s and then 1s and then 2s
I hope it is correct
#Post#: 442--------------------------------------------------
Re: linked list sort
By: dinesh Date: February 6, 2013, 12:27 am
---------------------------------------------------------
yes it is correct
Can you think of another method?
*****************************************************