单链表Single-LinkList

0、节点结构体定义

typedef struct LNode{int data;struct LNode *next;} Lnode, *LinkList;

1、初始化

bool InitList(LinkList &L)	//初始化 
{L = new LNode;if(!L){return false;}L->next = NULL;return true;
}

2、创建

（1）头插法

void CreateList_H(LinkList &L, int n)	//头插法创建 
{LinkList s;while(n--){	//--n不行！！ s = new LNode;cin>> s->data;s->next = L->next;		//链表的i++ L->next =s;	}
}
//反复利用链表头L和新节点s添加（就是插入...） 

（2）尾插法

void CreateList_R(LinkList &L, int n)	//尾插法创建 
{LinkList s, r = L;while(--n){s = new LNode;cin>> s->data;r->next = s;			//链表的i++s->next = NULL;r = s;}
}
//利用r存储当前节点信息，便利于新节点s的添加 

3、查找

（1）查找具体元素

bool Finde(LinkList &L, int e)	//查找具体元素 
{LinkList p = L->next;while(p != NULL && p->data != e){p = p->next;}if(!p){return false;}return true;
}

（2）查找第 i 个元素

bool GetElemi(LinkList &L, int i, int &e)	//查找第i个元素 
{int j = 1;				//记不住就初始化为 j = 1、p = L LinkList p = L->next;  //因为后面都是这样（保对），而且也没增加什么时间 while(p && j<i){p = p->next;++j;}if(!p || j>i){		//i值不合法：i>n || i<0 return false;}e = p->data;		//用e记录元素i return true;
}

4、插入

bool ListInsert(LinkList &L, int i, int e) 	//在第i个元素后插入元素 
{int j = 0;LinkList p = L;	//保证能在第一个元素前插入 while(p && j<i){p = p->next;++j;}if(!p || j>i){return false;}//上面就是查找操作... LinkList s = new LNode;s->data = e;s->next = p->next;p->next = s;return true;
}

5、删除

bool ListDelete(LinkList &L, int i)	//删除第i个元素 
{int j = 0;LinkList p = L;		//保证能删除第 1个元素 while(p && j<i-1){p = p->next;++j;}if(!p ||j>i-1){return false;}//上面还是查找操作...（找第元素i-1）LinkList q = p->next;	//使用临时变量更安全！（p->next->next = p->next; delete p->next; p->next = q->next;	   //当n=2时会出错！因为要删除的p->next已经变成NULL了！） delete q;return true;
}

6、释放内存

bool ListRelese(LinkList &L)
{LinkList p;while(L){p = L;			//暂存当前节点 L = L->next;	//更新为下一节点 delete p;		//删除当前节点 /*这样也ok: **p = L->next;// 暂存下一个节点**delete L;// 删除当前节点**L = p;// 更新当前节点为下一个节点*/}return true;
}

7、其他操作

（1）查找中间元素

LinkList FindMid(LinkList L)	//查找中间的节点 
{						//不会修改L就不用传引用！LinkList p = L, q = L;while(p){q = q->next;p = p->next->next;}return q;
}

（2）查找倒数第 k 个节点

LinkList Findk(LinkList L, int k)	//查找倒数第k个节点 
{LinkList p, q;p=L->next; q=L->next; while(p->next!=NULL){if(--k<=0) //k减到0时，慢指针开始走q=q->next; p=p->next; //p为快指针，先走k-1步}if(k>0)return NULL;elsereturn q; 
}

（3）合并有序链表

/合并有序链表：将两个有序（非递减）单链表La和Lb合并为一个新的有序（非递减）单链表Lc 
LinkList ListMerge(LinkList LA, LinkList LB)
{LinkList p = LA->next ,q = LB->next; LinkList LC = LA, r = LC;while(p && q){if(p->data > q->data){r->next = q;r = q;q = q->next;}else{r->next = p;r = p;p = p->next;}}r->next = p? p:q;delete LB;return LC;
} 

（4）逆转链表

void ListReverse(LinkList &L)	//逆转单链表 
{LinkList p = L->next, q;L->next = NULL;while(p){q = p->next;p->next = L->next;L->next = p;p = q;} 
}