Unofficial C Solution to Problem 2.4 in Cracking the Coding Interview (5th Edition)

25 Apr

The question is one step in the quick sort algorithm. The idea is to rearrange the list so that the smaller nodes than pivot are previous to all other nodes. More details could be found on Wikipedia. In the implements in the book, the author has to take extremely care of the NULL pointer. But in my implement, thanks to the head node, I do not have such issue. Additionally, the smaller-node list increases from head to tail, and the not-smaller-node list grows from tail to head. At the end, we can easily concatenate these two temporary lists without any more travels, which the official solution needs.

Leave a Reply

Your email address will not be published. Required fields are marked *