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

typedef struct ListNode {
	int data;
	struct ListNode *next;
} ListNode;

typedef ListNode *List;

List newNode(int data)
{
	List ret = (List)malloc(sizeof(ListNode));
	
	ret->data = data;
	ret->next = NULL;
	
	return ret;
}

void deleteNode(ListNode *node)
{
	free(node);
}

void pushFront(List *list, int data)
{
	ListNode *node = newNode(data);
	
	node->next = *list;
	*list = node;
}

void deleteList(List *list)
{
	while (*list) {
		ListNode *next = (*list)->next;
		deleteNode(*list);
		*list = next;
	}
}

void printList(List l)
{
	while (l) {
		printf("%d", l->data);
		l = l->next;
		
		if (l) {
			printf(" ");
		}
	}
	
	printf("\n");
}

int count(List list)
{
	if (list) {
		return count(list->next)+1;
	}
	
	return 0;
}

ListNode* reverseList(List *list)
{
	ListNode *first;
	ListNode *last;
	
	if (*list==NULL || (*list)->next==NULL) {
		return *list;
	}
	
	last = reverseList(&((*list)->next));
	last->next = *list;
	first = (*list)->next;
	(*list)->next = NULL;
	*list = first;
	last = last->next;
	
	return last;
}

#ifdef TEST
#define NODES_NUM 5
#else
#define NODES_NUM 100000000
#endif

int main() {
	List l = NULL;
	
	for (int i=1; i<=NODES_NUM; ++i) {
		pushFront(&l, i);
	}
	
	printf("Original list has %d elements.\n", count(l));
#ifdef TEST
	printList(l); // Just for testing for small lists.
#endif
	reverseList(&l);
	printf("Reversed list has %d elements.\n", count(l));
#ifdef TEST
	printList(l); // Just for testing for small lists.
#endif
	deleteList(&l);
	
	return EXIT_SUCCESS;
}