#include <iostream>
#include <iomanip>
using namespace std;

typedef struct node
{
	int val;
	node *next;
}node;
node * create_list();
void traverse_list(node *pHead);
int  get_len_list(node *pHead);
bool delete_list(node *pHead,int pos,int &val);
bool insert_list(node *pHead,int pos,int val);
void sort_list(node *pHead);
void reverse_list(node *PHead);
void main()
{
	node *pHead = create_list();
    int len = get_len_list(pHead);
	cout<<"list length:"<<len<<endl;
	traverse_list(pHead);
	int val;
	delete_list(pHead,6,val);
	cout<<"被删除的值为："<<val<<endl;
	traverse_list(pHead);
	insert_list(pHead,3,9);
	insert_list(pHead,1,7);
	traverse_list(pHead);
	sort_list(pHead);
	traverse_list(pHead);
	reverse_list(pHead);
	traverse_list(pHead);
}

node * create_list()
{
	int len = 6,i;
	node *pHead = new node,*pTail,*pNew;
// 	cout<<"请输入创建链表的节点数：";
// 	cin>>len;
	pTail = pHead;
	pHead->next = NULL;
	for (i=0;i<len;i++)
	{
		//cout<<"输入第"<<setw(2)<<i<<"节点的值：";
		pNew = new node;
		//cin>>pNew->val;
		pNew->val = i+1;
		pTail->next = pNew;
		pTail = pNew;
	}
	pTail->next = NULL;
	return pHead;
}

void traverse_list(node *pHead)
{
	node *p = pHead->next;
	while (p)
	{
		cout<<p->val<<" ";
		p = p->next;
	}
	cout<<endl;
}

//取得节点个数，不包括头节点
int  get_len_list(node *pHead)
{
	node *p = pHead->next; //指向第一个节点
	int len = 0;
	while(p)
	{
		++len;
		p = p->next;
	}
	return len;
}
//删除第pos个节点，pos从首节点开始计数
bool delete_list(node *pHead,int pos,int &val)
{
	node *p = pHead;
	int i = 1;
	while (NULL != p->next && i < pos) //找到删除节点之前的一个节点
	{
		p = p->next;
		i++;
	}
	if (i > pos || NULL == p->next)//
	{
		return false;
	}
	node * q = p->next;
	val = q->val;
	p->next = q->next;
	delete q;
    return true;	
}
bool insert_list(node *pHead,int pos,int val)
{
	node *p = pHead;
	int i = 1;
	while(NULL != p->next && i < pos)
	{
		++i;
		p = p->next;
	}
	if (i > pos /*|| NULL ==  p->next*/) 	
	{ 
		return false;
	}
	node *pNew = new node;
	pNew->val = val;
	pNew->next = p->next;
	p->next = pNew;
	return true;
}
//升序排序
void sort_list(node *pHead)
{
     node *p = pHead->next,*q;
	 int tmp;
	 while (p)
	 {
		 q= p->next;
		 while(q)
		 {
			 if (p->val > q->val)
			 {
				 tmp = p->val;
				 p->val = q->val;
				 q->val = tmp;
			 }
			 q= q->next;
		 }
		 p = p->next;
	 }
}

void reverse_list(node *pHead)
{
	node *p = pHead,*q1,*q2,*q3,*tempq1;
	q1 = pHead->next;
	tempq1 = q1;
	q2 = q1->next;
	while (q2)
	{
		q3 = q2->next;
		q2->next = q1;
		q1 = q2;
		q2 = q3;
	}
	pHead->next = q1;
	tempq1->next = NULL;
}