Implement the quicksort algorithm on lists. You write one function

struct listnode * sort(struct listnode * a);

with

struct listnode { struct listnode * next; int key;};

It takes a list, and returns the list in sorted sequence. You change only pointers, DO NOT allocate new nodes or move key values to different nodes.

test code:

#include  #include  struct listnode { struct listnode * next; long key; } ; int main(void) { long i; struct listnode *node, *tmpnode, *space; space = (struct listnode *) malloc( 500000*sizeof(struct listnode)); for( i=0; i< 500000; i++ ) { (space + i)->key = 2*((17*i)%500000); (space + i)->next = space + (i+1); } (space+499999)->next = NULL; node = space; printf(" prepared list, now starting sort "); node = sort(node); printf(" checking sorted list "); for( i=0; i < 500000; i++) { if( node == NULL ) { printf("List ended early "); exit(0); } if( node->key != 2*i ) { printf("Node contains wrong value "); exit(0); } node = node->next; } printf("Sort successful "); exit(0); }