I like your code. I understand it better than mine. But you don't save any pointer to the start of the memory allocated for 'r' and 'q', so you could never free this memory.

I forgot free(part)
Anyway, I'm not very proud of this code. It's difficult to read and I admit than sometimes it fails one of the random tests.