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


struct node
{
	unsigned int elem;
	struct node *next;
};


struct node *head = NULL;
struct node *tail = NULL;

void create_list(unsigned int elem);
void insert_node(int pos, unsigned int elem);
void delete_node(int pos);
void print_linklist(struct node *linklist_head);
int search(unsigned int elem);
int find_mid(struct node *linklist_head);
int find_last_nth(struct node *linklist_head, int n);
void reverse_linklist(struct node *linklist_head);



int main(void)
{
	int n;

	create_list(1);
	create_list(2);
	create_list(3);
	create_list(4);
	create_list(5);
	create_list(6);
	create_list(7);
	create_list(8);
	create_list(9);
	create_list(10);
	print_linklist(head);

	reverse_linklist(head);
	print_linklist(head);

	return 0;
}




void create_list(unsigned int elem)
{
	struct node *p = (struct node *)malloc(sizeof(struct node));
	p->elem = elem;
	p->next = NULL;

	if(head == NULL)
		head = p;
	else
		tail->next = p;

	tail = p;
}

void insert_node(int pos, unsigned int elem)
{
	struct node *pre;
	pre = head;
	int i = 0;
	struct node *p = (struct node *)malloc(sizeof(struct node));

	if(pos == 0)
	{
		p->elem = elem;
		p->next = head;
		head = p;
	}
	else
	{
		while(i < pos - 1)
		{
			pre = pre->next;
			i++;
		}

		p->elem = elem;
		p->next = pre->next;
		pre->next = p;
	
		if(p->next == NULL)
			tail = p;
	}
}

void delete_node(int pos)
{
	struct node *pre, *p;
	pre = head;
	int i = 0;

	if(pos == 0)
	{
		head = head->next;
		free(pre);
	}
	else
	{
		while(i < pos - 1)
		{
			pre = pre->next;
			i++;
		}
	
		p = pre->next;
		pre->next = p->next;
		if(p->next == NULL)
			tail = pre;
		free(p);
	}
}

void print_linklist(struct node *linklist_head)
{
	struct node *p;

	for(p = linklist_head; p; p = p->next)
		printf("%5d", p->elem);

	printf("\n");
}

int search(unsigned int elem)
{
	struct node *p;

	for(p = head; p; p = p->next)
		if(p->elem == elem)
			return 1;
	return 0;
}

int find_mid(struct node *linklist_head)
{
	struct node *p;
	struct node *q;
	p = q = linklist_head;

	while(p != NULL && p->next != NULL)
	{
		p = p->next->next;
		q = q->next;
	}

	return q->elem;
}

int find_last_nth(struct node *linklist_head, int n)
{
	int i;

	struct node *p;
	struct node *q;

	p = q = linklist_head;

	for(i = 0; i < n-1; i++)
		p = p->next;

	while(p->next != NULL)
	{
		p = p->next;
		q = q->next;
	}

	return q->elem;
}

void reverse_linklist(struct node *linklist_head)
{
	struct node *p,*n;
    //需要考虑没有节点或者只有一个节点的情况，不然遇到这个情况会发生段错误
    if ((linklist_head == NULL) || (linklist_head->next == NULL))
		return;
	p = linklist_head->next; //p指针指向第2个节点
	linklist_head->next = NULL;//第一个节点的指针域为NULL，作为尾节点
	while (p->next != NULL) //p指针的下一个节点不为NULL
	{
		n = p->next;  //保存p节点的下一个节点的地址
		p->next = linklist_head;  //p节点的指针域指向第一个节点
		linklist_head = p;//头节点指向p节点，p节点作为我们首节点
		p = n; //p指针指向下一个节点
	}
		p->next = linklist_head;  //当p指针的指针域为null，我们让它指针第一个节点
		linklist_head = p; //头指针指向p节点
		head = linklist_head;//linklist_head是局部变量,我们需要改变一下全局变量head;
}