#include <stdio.h>

// see http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
// and  http://www.glenmccl.com/tip_005.htm
// and http://cslibrary.stanford.edu/105/

struct node {
	int data;
	struct node* next;
} ;

struct node* removeNth(struct node* list, int n) {
	struct node* p;
	struct node* back;
	struct node* front;

	if (list != NULL) {
		if (n == 0) {
			p = list;
			list = list->next;
			free(p);
		}
		else {
			back = list;
			front = list->next;
			while(n > 1 && front->next != NULL) {
					
				//... complete this
				n--;
			}
			// ...statement goes here
			//free(front);  
		}
	}
		
	return list;
}

struct node*  removeNthRec(struct node* list, int n) {
	// This recursive version works
	struct node* p;
		
	if (list != NULL) {
		if (n == 0) {
			p = list;
			list = list->next;
			free(p);
			return list;
		}
		else {
			list->next = removeNthRec(list->next, n-1);
			return list;
		}
	}
	else 
	    return list;
}

void printList(struct node* list) {
	struct node* p;
	p = list;
	while (p != NULL) {
		printf("%3d", p->data);
		p = p->next;
	}
	printf("\n");
}
				
struct node* addNode(struct node* list, int val) {
	struct node* p;
		
	p = (struct node*)malloc(sizeof(struct node));
	p->data = val;
	p->next = list;

	return p;
}

struct node* addNodeLast(struct node* list, int val) {
	struct node* temp;
	struct node* p;
		
	temp = (struct node*)malloc(sizeof(struct node));
	temp->data = val;
	temp->next = NULL;
	
	if (list == NULL)
		list = temp;
	else {
		p = list;
		// ...complete this

	}
		
	return list;
}

int main() {
	struct node* head;
	int i;

	head = NULL;
// add some entries to list
	for (i = 1; i <= 10; i++) {
	      head = addNode(head, i);
	//      head = addNodeLast(head, i);
	}
	
 	printList(head);	
	
	head = removeNth(head, 0);
        printList(head);
		
	head = removeNth(head, 3);
        printList(head);
		
	head = removeNth(head, 7);
        printList(head);

	head = removeNthRec(head, 0);
        printList(head);

	head = removeNthRec(head, 2);
        printList(head);

	head = removeNthRec(head, 4);
        printList(head);

	head = removeNthRec(head, 4);
        printList(head);
	
	return 0;
}