链表操作

单链表for()循环的两种初始化：

1. for(Node *p=plist; p->next !=NULL; p=p->next)

//进行插入，删除操作，对链表进行修改

2. for(Node *p=plist->next; p !=NULL; p=p->next)

//不对链表进行修改

单链表常考：

单链表插入的两种方法：

//头插 
bool Insert_head(List plist,int val) 
{
    Node *p=(Node*)malloc(sizeof(Node));
    p->data=val; 

    assert(p != NULL); 
    if(p==NULL) 
        return false; 

    p->next=plist->next; 
    plist->next=p; 
    return true; 
}

//尾插 
bool Insert_tail(List plist,int val) 
{
    Node *p=(Node*)malloc(sizeof(Node)); 
    p->data=val; 

    assert(p != NULL); 
    if(p==NULL) 
        return false; 

    Node *q=plist; 
    while(q->next != NULL) //找尾巴 
    { 
        q=q->next; 
    } 

    //给q后面插p 
    p->next=q->next; 
    q->next=p; 
    return true; 
} 

销毁单链表：

//销毁链表
void Destory(List plist)
{
	//*****************************************way1************************************//
	//每次都删头结点之后的结点，当plist->next!=NULL，说明还有还有结点没有处理

	Node *p;
	while(plist->next !=NULL)
	{
		p=plist->next;
		plist->next=p->next;
		free(p);
	}

	//**************************************way2***************************************//
	//从第一个数据域开始一个一个删
	/*Node *p=plist->next;
	Node *q;
	while(p != NULL)
	{
		q=p->next;
		free(p);
		p=q;
	}
	plist->next=NULL;*/   //头结点制空
}

单链表逆置：

//逆置 
void Reverse(List plist) 
{ 
    //指针为空退出，只有一个头结点退出，只有一个数据结点退出，不需逆置 
    if(plist == NULL || plist->next==NULL || plist->next->next==NULL) 
        return ;            

//***************************************way1***********************************// 
    //利用头插法实现逆置 
    //按原来结点的顺序利用头插法再插入链表 
    //时间复杂度O(n),最好 
    Node *p=plist->next; 
    Node *q; 
    plist->next=NULL; 
    while(p !=NULL) 
    { 
        q=p->next; 
        p->next=plist->next; 
        plist->next=p; p=q; 
     } 
//**************************************way2*******************************// 
    //结点不动，第一个结点的数据域与最后一个结点的数据域的值交换， 
    //第二个结点的数据域与倒数第二个结点的数据域交换，以此类推 
    //时间复杂度O(n^2) 
    /*Node *p=plist->next; 
    Node *q; 
    for(q=plist;q->next !=NULL;q=q->next); 
    for(int i=0;i<GetLength(plist)/2;i++) 
    { 
        int tmp; 
        tmp=p->data; 
        p->data=q->data; 
        q->data=tmp; 
        p=p->next; 
        q=GetPri(plist,q);//q的前驱赋给q 
    }*/ 
//*****************************************way3******************************// 
    //改变指针的指向，后->前，头指针指向最后一个结点 //时间复杂的O(n) 
    /*Node *p=plist->next; 
    Node *q=p->next; 
    Node *s; 
    p->next=NULL; 
    while(q !=NULL) 
    { 
        s=q->next; 
        q->next=p; 
        p=q; 
        q=s; 
    } 
    plist->next=p;*/ 
}