A silly (and rather naive) implementation for a test question I stumbled upon these days. The subject was (obviously) Data Structures.

reverse-flist-inplace.c

/*----------------------------------------------------------------------------------------------------
 * flist.h : Library header
 */


#ifndef FLIST_H_
#define FLIST_H_


#include <stddef.h>


typedef struct Flist Flist;
typedef struct FlistNode FlistNode;

int FlistNode_value(const FlistNode* LN);
FlistNode* FlistNode_next(const FlistNode* LN);

Flist* Flist_new(void);
Flist* Flist_delete(Flist* L);
int Flist_empty(const Flist* L);
size_t Flist_size(const Flist* L);
void Flist_push(Flist* L, int value);
void Flist_pushall(Flist* L, size_t nargs, ...);
FlistNode* Flist_geti(const Flist* L, size_t idx);
FlistNode* Flist_begin(const Flist* L);
FlistNode* Flist_end(const Flist* L);
void Flist_revertvalues(Flist* L);
void Flist_revertnodes(Flist* L);
int Flist_compare(const Flist* L1, const Flist* L2);


#endif /* FLIST_H_ */


/*----------------------------------------------------------------------------------------------------
 * flist.c : Library implementation
 */


#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>


struct FlistNode {

	struct FlistNode* next;
	int value;
};


struct Flist {

	FlistNode* first;
	FlistNode* last;
};


static FlistNode* FlistNode_new(int value);
void Flist_print(Flist* L, FILE* F);


int FlistNode_value(const FlistNode* LN) {
	return LN->value;
}


FlistNode* FlistNode_next(const FlistNode* LN) {
	return LN->next;
}


FlistNode* Flist_begin(const Flist* L) {
	return L->first;
}


FlistNode* Flist_end(const Flist* L) {
	return L->last;
}


Flist* Flist_new(void) {

	return (Flist*) calloc(1, sizeof(Flist));
}


Flist* Flist_delete(Flist* L) {

	FlistNode* p = L->first;
	FlistNode* t;
	while (NULL != p) {
		t = p->next;
		free(p);
		p = t;
	}
	free(L);
}


int Flist_empty(const Flist* L) {

	return NULL == L->first;
}


size_t Flist_size(const Flist* L) {

	size_t size = 1;
	FlistNode* p = L->first;
	if (NULL == p) return 0; // list is empty
	for (; p != L->last; p = p->next, ++size);
	return size;
}


void Flist_push(Flist* L, int value) {

	FlistNode* LN = FlistNode_new(value);

	if (NULL != LN) {
		if (Flist_empty(L)) {
			L->first = LN;
			L->last = LN;

		} else {
			L->last->next = LN;
			L->last = LN;
		}
	}
}


void Flist_pushall(Flist* L, size_t nargs, ...) {

	size_t i;
	va_list args;
	va_start(args, nargs);
	for (i = 0; i < nargs; ++i) {
		Flist_push(L, va_arg(args, int));
	}
}


FlistNode* Flist_geti(const Flist* L, size_t idx) {

	size_t pos = 0;
	FlistNode* p = L->first;
	for (; pos != idx && p != L->last; p = p->next, ++pos);
	if (pos == idx) return p;
	return NULL;
}


void Flist_revertvalues(Flist* L) {                        /* n + (n/2) * (n/2)! */

	/* n     */ size_t size = Flist_size(L);               /* n */
	/* 1     */ size_t ihead = 0;
	/* 1     */ size_t itail = size - 1;
	/* 1     */ FlistNode* phead = L->first;
	/* 1     */ FlistNode* ptail = L->last;
	/* -     */ int i;
	/* 1     */ if (size < 2) return;
	/* n/2   */ while (itail > ihead) {                    /* (n / 2) * ((n - 1) * ... * (n / 2)) = (n/2) * (n/2)! 
	/* 1     */     i = phead->value;
	/* 1     */     phead->value = ptail->value;
	/* 1     */     ptail->value = i;
	/* 1+1   */     ihead++; phead = phead->next;
	/* 1+n2  */     itail--; ptail = Flist_geti(L, itail);
	/* -     */ }
}


void Flist_revertnodes(Flist* L) {                  /* n! */

	/* 1  */ FlistNode* phead = L->last;
	/* 1  */ FlistNode* ptail = L->last;
	/* -  */ FlistNode *p, *penultimate;
	/* 1  */ if (L->first == L->last) return;
	/* n  */ while (ptail != L->first) {            /* n * (n-1) * ... * 1 = n! */
	/* n2 */ 	for (p = L->first;
	/*    */ 		 p != ptail;
	/*    */ 		 penultimate = p, p = p->next);
	/* 1  */ 	ptail->next = penultimate;
	/* 1  */ 	ptail = penultimate;
	/* 1  */ }
	/* 1  */ ptail->next = NULL;
	/* 1  */ L->first = phead;
	/* 1  */ L->last = ptail;
}


int Flist_compare(const Flist* L1, const Flist* L2) {
	int cmp = 0;
	FlistNode* p1 = L1->first;
	FlistNode* p2 = L2->first;
	while (cmp == 0 && p1 && p2) {
		cmp = (p1->value > p2->value) - (p2->value > p1->value);
		p1 = p1->next;
		p2 = p2->next;
	}
	if (cmp == 0) {
		if (p1 == NULL && p2 != NULL) cmp = -1;
		else if (p2 == NULL && p1 != NULL) cmp = 1;
	}
	return cmp;
}


void Flist_print(Flist* L, FILE* F) {

	FlistNode* LN = L->first;
	const char *sep = "";
	fprintf(F, "[");
	while (NULL != LN) {
		fprintf(F, "%s%d", sep, LN->value);
		sep = ", ";
		LN = LN->next;
	}
	fprintf(F, "]\n");
}


static FlistNode* FlistNode_new(int value) {

	// Cast not really necessary for C compilers, but my editor uses a C++ compiler
	// and I'm lazy.
	FlistNode *LN = (FlistNode*) calloc(1, sizeof(FlistNode));
	if (NULL != LN) {
		LN->value = value;
	}
	return LN;
}



/* -------------------------------------------------------------------------------------------------
 * main.c : Main (executable) part
 */


#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <time.h>
#include <signal.h>


#define LIST_SIZE 10000
#define NPASSES 100

#define DURATION(v) ( ( ((float)(v)) * (results->num) ) / (results->den) )

typedef struct Options {

	int skipTests;
	size_t listSize;
	size_t npasses;
	FILE* outf;
	FILE* errf;
} Options;


typedef struct Results {

	int id;
	const char* name;
	size_t npasses;
	size_t listSize;
	clock_t num; /* 1 */
	clock_t den; /* CLOCKS_PER_SEC */
	clock_t min;
	clock_t max;
	clock_t avg;
} Results;


static Options opts;
static void init(int argc, char** argv);
static void quit();
static void onSignal(int sig);

static int testCorrectness(const Options* opts, size_t listSize);
static void measureTimings(const Options* opts);
static void measureTimingsFor(const Options* opts, void* L, void(*testFn)(void*), Results* results);
static void exportTimings(const Options* opts, const Results* results);

static int pout(const Options* opts, const char* fmt, ...);
static int perr(const Options* opts, const char* fmt, ...);


int main(int argc, char** argv) {

	size_t i;
	int correct = 1;
	init(argc, argv);
	signal(SIGTERM, onSignal);
	signal(SIGINT, onSignal);
	for (i = 0; !opts.skipTests && correct && i <= 5; ++i) {
		correct = testCorrectness(&opts, i);
	}
	if (!correct) {
		perr(&opts, "Tests are incorrect. Aborting.\n");
		return 1;
	}
	measureTimings(&opts);
	return 0;
}


static void init(int argc, char** argv) {

	size_t i;
	const char* arg;

	opts.skipTests = 0;
	opts.listSize = LIST_SIZE;
	opts.npasses = NPASSES;
	opts.outf = stdout;
	opts.errf = stderr;

	for (i = 1; i < argc; arg = argv[i++]) {
		arg = argv[i];
		if (arg[0] == '-') {
			arg = arg + 1;
			switch(arg[0]) {
			case 't': opts.skipTests = 0; break;
			case 'T': opts.skipTests = 1; break;
			case 's': opts.listSize = atoi(++arg); break;
			case 'p': opts.npasses = atoi(++arg); break;
			case 'o': opts.outf = fopen(++arg, "w+"); break;
			case 'e': opts.errf = fopen(++arg, "w+"); break;
			case 'O': opts.outf = tmpfile(); break;
			case 'E': opts.errf = tmpfile(); break;
			}
		}
	}
}


static void quit() {

	if (opts.outf != stdout) fclose(opts.outf);
	if (opts.errf != stderr) fclose(opts.errf);
}


static void onSignal(int sig) {

	perr(&opts, "\n*** %s. Freeing resources.\n", sig == SIGTERM ? "Terminated" : "Interrupted");
	quit();
	exit(2);
}


static int testCorrectness(const Options* opts, size_t listSize) {

	size_t i;
	int correct = 1;
	Flist* L = Flist_new();
	Flist* L_normal = Flist_new();
	Flist* L_inverse = Flist_new();

	for (i = 0; i < listSize; ++i) {
		Flist_push(L, i + 1);
		Flist_push(L_normal, i + 1);
		Flist_push(L_inverse, listSize - i);
	}

	perr(opts, "Testing correctness with list size %d.\n", listSize);

	if (correct) {
		correct = Flist_compare(L, L) == 0;
		perr(opts, "\tThe comparison function is %s.\n",
			correct ? "correct" : "incorrect");
	}

	if (correct) {
		correct = Flist_size(L) == listSize 
				&& Flist_size(L_normal) == listSize 
				&& Flist_size(L_inverse) == listSize;
		perr(opts, "\tThe sizes of the generated lists are %s.\n",
			correct ? "correct" : "incorrect");
	}

	if (correct) {
		Flist_revertvalues(L);
		correct = Flist_compare(L, L_inverse) == 0;
		perr(opts, "\tRevert by value is %s.\n",
			correct ? "correct" : "incorrect");
	}

	if (correct) {
		Flist_revertnodes(L);
		correct = Flist_compare(L, L_normal) == 0;
		perr(opts, "\tRevert by nodes is %s.\n",
			correct ? "correct" : "incorrect");
	}

	Flist_delete(L);
	Flist_delete(L_normal);
	Flist_delete(L_inverse);

	return correct;
}


static void measureTimings(const Options* opts) {
#	define STRQT(s) #s
#	define STRFY(s) STRQT(s)
#	define EXEC(_idx_, _fname_) \
		results[_idx_].id = _idx_; \
		results[_idx_].name = STRFY(_fname_); \
		perr(opts, "Testing timings for " STRFY(_fname_) \
		                " with list size %d in %d sort(s)...\n", \
			opts->listSize, opts->npasses); \
		measureTimingsFor(opts, L, (void(*)(void*))_fname_, &results[_idx_]); \
		exportTimings(opts, &results[_idx_])

	Flist* L = Flist_new();
	size_t i;
	for (i = 0; i < opts->listSize; ++i) Flist_push(L, i + 1);
	Results results[2] = {0};

	EXEC(0, Flist_revertnodes);
	EXEC(1, Flist_revertvalues);

#	undef STRQT
#	undef STRFY
#	undef EXEC
}


static void measureTimingsFor(const Options* opts, void* L, void(*testFn)(void*), Results* results) {

	clock_t start, stop, diff, min = -1, max = -1, avg = -1;
	size_t i;

	results->listSize = opts->listSize;
	results->npasses = opts->npasses;
	results->num = 1;
	results->den = CLOCKS_PER_SEC;

	for (i = 0; i < opts->npasses; ++i) {
		size_t count = i + 1;

		perr(opts, "\tExecuting pass %d... ", i);
		start = clock();
		testFn(L);
		stop = clock();

		diff = stop - start;
		perr(opts, " Duration: %f second(s)", DURATION(diff));

		if (avg != -1) {
			avg = (avg * (count - 1) + diff) / count;			
		} else {
			avg = diff;
		}

		perr(opts, ", average: %f second(s)", DURATION(avg));

		if (max == -1 || diff > max) {
			if (max != -1) perr(opts, " (slowest)");
			max = diff;
		}

		if (min == -1 || diff < min) {
			if (min != -1) perr(opts, " (fastest)");
			min = diff;
		}

		perr(opts, "\n");
	}

	results->min = min;
	results->max = max;
	results->avg = avg;
}


static void exportTimings(const Options* opts, const Results* results) {

	pout(opts, "%d" /* id */
	           "\t%s" /* name */
	           "\t%d" /* listSize */
	           "\t%d" /* npasses */
	           "\t%ld" /* avg */
	           "\t%ld" /* min */
	           "\t%ld" /* max */
	           "\t%ld" /* num */
	           "\t%ld" /* den */
	           "\t%03.9lf" /* avg (in secs) */
	           "\n",
		results->id,
		results->name,
		results->listSize,
		results->npasses,
		results->avg,
		results->min,
		results->max,
		results->num,
		results->den,
		DURATION(results->avg)
	);
}


static int pout(const Options* opts, const char* fmt, ...) {
	va_list args;
	va_start(args, fmt);
	int ret = vfprintf(opts->outf, fmt, args);
	va_end(args);
	return ret;
}


static int perr(const Options* opts, const char* fmt, ...) {
	va_list args;
	va_start(args, fmt);
	int ret = vfprintf(opts->errf, fmt, args);
	va_end(args);
	return ret;
}