#include <stdio.h>
#include <stdlib.h>
struct node{
	int data;
	struct node* next;
}*p;
struct node*  (*build)();
void push(struct node **headref, int data){
	struct node *temp = NULL;
	temp = malloc(sizeof(struct node));
	temp->data = data;
	temp->next = *headref;
	*headref = temp;
}
struct node* build_spl_case_add_tail(){
	struct node* head = NULL;
	struct node* tail;
	int i=0;
	
	push(&head,1);
	tail = head;
	
	for(i=2;i<6;i++){
		push(&(tail->next),i);		//better than traversing the linked list every time till the end 
		tail=tail->next;
	}
	return head;
}

struct node* build_with_dummy(){
	struct node dummy;
	struct node* tail = &dummy;
	int i;
	dummy.next = NULL;
	
	for(i=1;i<6;i++){
		push(&(tail->next),i);
		tail = tail->next;
	}
	return dummy.next;			//return value needs to be a pointer which is dummy.next, dummy.data should have garbage
}
struct node* build_local_ref(){
	struct node *head = NULL;
	struct node **lastptref = &head;
	int i;
	for(i=1;i<6;i++){
		push(lastptref,i);
		lastptref = &((*lastptref)->next);
	}
	return head;
}
void append_node(struct node ** headref, int num){
	struct node* current = *headref;
	struct node* newnode;
	
	newnode = malloc(sizeof(struct node));
	newnode->data =num;
	newnode->next = NULL;
	if(current == NULL){
		*headref = newnode;
	}
	else{
		while(current->next!=NULL){
			current = current->next;
		}
		current->next = newnode;
	}
}
void append_node_with_push(struct node **headref, int num){
	struct node* current = *headref;
	
	if(current == NULL)
		push(headref,num);
	else{
		while(current->next != NULL){
			current = current->next;
		}
		push(&(current->next),num);
	}
}
struct node* copylist(struct node *head){
	struct node* newlist = NULL;
	struct node* current = head;
	struct node* tail, *temp;;
	while(current!=NULL){
		if(newlist==NULL){
			newlist = malloc(sizeof(struct node));
			newlist->data = current->data;
			newlist->next = NULL;    //newlist->next = curent->next wrong way because newlist points to the nodes of currentlist
			tail = newlist;
		}
		else{
		/*	while(tail->next!=NULL)
				tail=tail->next;
			temp = malloc(sizeof(struct node));					//APPROACH #1
			temp->data = current->data;
			temp->next = NULL;
			tail->next = temp;*/
			
			tail->next = malloc(sizeof(struct node));
			tail = tail->next;
			tail->data = current->data;					//APPROACH #2 low complexity
			tail->next = NULL;
			

		}
		current= current->next;
	}
	return newlist;
}

struct node* copylist_withpush(struct node *head){
	struct node *newlist = NULL;
	struct node * current = head;
	struct node* tail;
	while(current!=NULL){
		if(newlist == NULL){
			push(&newlist,current->data);
			tail = newlist;
		}			
		else{
			push(&(tail->next),current->data);
			tail = tail->next;
		}
		current = current->next;
	}
	return newlist;
}

struct node* copylist_withdummy(struct node *head){
	struct node dummy;
	struct node *current = head;
	dummy.next = NULL;
	struct node* tail;
	tail = &dummy;
	
	while(current!=NULL){
			push(&(dummy.next),current->data);
			tail = tail->next ;
		}
		current = current->next;
	return dummy.next;
}
struct node* copylist_with_localref(struct node* head){
	struct node *current = head ;
	struct node *newlist = NULL;
	struct node **lastptr;
	lastptr = &newlist;	
	while(current!=NULL){
			push(lastptr,current->data);
			lastptr = &((*lastptr)->next);
			current = current->next;
	}
	return newlist;
}

struct node* copylist_rec(struct node*head){
	struct node * current = head;
	if(head == NULL) return NULL; //termination conditino for recursive function
	else
	{
		struct node* newlist = malloc(sizeof(struct node));
		push(&newlist,current->data);
		newlist->next = copylist_rec(current->next);
		return newlist;
	}
}

	
main(){
	struct node *result, *copy;
	result = build_spl_case_add_tail();
	while(result!=NULL){
		printf("%d\t",result->data);
		result=result->next;
	}
	result = build_with_dummy();
	result = build_local_ref();
	append_node(&result,23);
	append_node_with_push(&result,232);

	copy = copylist_rec(result);
	while(copy!=NULL){
		printf("%d\t",copy->data);
		copy = copy->next;
	}
	
	return 0;
}

1	2	3	4	5	1	2	3	4	5	23	232