我的链表笔记

题目：设计一个递归算法， 删除不带头结点的单链表L 中所有值为X的结点。

思路：递归查找，判断节点值是否相等，如相等删除即可！

代码：

//递归删除X 
void DeleteNodeWithValueX(int x,LinkList &L){
	//终止条件 
	if(L==NULL)return;
	//初始化A 
	LNode *a;
	//判断条件 当前L节点的值是否与给出的X相等 
	if(L->data == x){
		//A保存L的节点值 
		a = L;
		//L向后移动一位 
		L = L->next;
		//释放A 
		free(a);
		//继续递归，从被删除的后继继续往后遍历 
		DeleteNodeWithValueX(x,L);
	}else{
		//未找到相同值，继续递归 
		DeleteNodeWithValueX(x,L->next);
	}
} 

题目： 在带头结点的单表L 中，删除所有值为x 的结点，并释放其空间，假设值为的结点不唯一， 试编写算法以实现上述 *** 作。

思路：循环查找值为X的节点删除即可。

代码：

//带头节点删除X
void DeleteXWithHead(int x,LinkList &L){
	//初始化节点 a为暂存节点 p指向首个有元素的节点 pre保存前驱 
	LNode *a,*p = L->next,*pre=L;
	//遍历链表 
	while(p){
		//如果匹配值 
		if(p->data == x){
			//a节点暂存当前节点 
			a = p;
			//p向后遍历 
			p = p->next;
			//前驱指向p的后继 
			pre->next = p;
			//释放当前节点 
			free(a);
		}else{
			//前驱更新 
			pre = p;
			//节点指向更新 
			p=p->next;
		}
	}
} 

题目：设L 为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。

思路：利用栈先进后出的特性，对节点倒置打印即可。

代码：

//反向输出(利用栈 *** 作） 
void reverseLinkList(LinkList &L){
	//递归终止条件 
	if(L==NULL)return;
	//先压入栈内 
	reverseLinkList(L->next);
	//栈先进后出，现在后出打印链表即倒置 *** 作 
	if(L->data!=-1)printf("%d,",L->data); 
} 

题目：试编写在带头结点的单链表L 中删除一个最小值结点的高效算法（ 假设最小值结点是唯一的）

思路：遍历链表，比较值，保存值小的节点然后释放即可。

代码：

//删除最小值带头点的高效算法
int deleteminnode(LinkList &L){
	//初始化四个节点，minnode保存最小值的节点，p保存当前节点，pre保存最小值的前驱，q保存前驱节点 
	LinkList minnode = L,p = L->next,pre = L,q = L;
	//初始化x等于p的数据 
	int x = p->data;
	//循环遍历 
	while(p){
		//如果x比当前节点的值大，更新minnode 
		if(x > p->data){
			//x更新，保存最小值 
			x = p->data;
			//最小节点更新 
			minnode = p;
			//最小前驱更新 
			pre = q;
		}
		//前驱更新 
		q = p;
		//继续遍历 
		p=p->next;
	}
	//删除 *** 作 
	pre->next = minnode->next;
	//释放最小值节点 
	free(minnode); 
	//返回值
	return x; 
} 

题目：试编写算法将带头结点的单链表就地逆置，所谓 “就地”，是指辅助空间复杂度为O(1).

思路：遍历一遍链表，将节点的next指向倒置，需要三个指针，注意防止断链。

代码：

//就地逆转（头插法）
void reverseL(LinkList &L){
	//初始化三个节点，分别指向尾部，当前节点，当前节点的下一个节点 
	LNode *pre = NULL,*cur = L->next,*tem = cur->next;
	//循环遍历链表 
	while(cur){
		//tem移动到下一个节点，保存后面的节点，防止断链 
		 tem = cur->next;
		 //当前节点指向前一个节点 
		 cur->next = pre;
		 //前一个节点更新 
		 pre = cur;
		 //当前节点移到下一个节点 
		 cur = tem; 
	}
	//头节点更新 
	L->next = pre;
} 

题目： 有一个带头结点的单链表L ，设计一个算法使其元素递增有序。

思路:使用插入排序对链表重新插入一遍，您也可以考虑使用额外的辅助空间构建一个新的链表。

具体难理解的话可以戳这里：（我也感觉有点难）

感谢力扣作者~

【LeetCode 每日一题】147. 对链表进行插入排序 | 手写图解版思路 + 代码讲解

代码：

//排序链表（插入排序算法）
void insertsort(LinkList &L){
	//构造三个节点地址 cur代表当前节点，pre代表有序表的前驱，nextp保存当前节点的下一个地址 
	LNode *cur = L->next,*pre,*nextp;
	//nextp保存当前节点的下一个地址 
	nextp=cur->next;
	//有序表的首个节点，令其next指针为空，以防循环不结束 
	cur->next = NULL;
	//当前指针指向下一个节点，即无序表的首个节点 
	cur = nextp;
	//开始遍历 
	while(cur){
		//nextp保存cur的next指针，防止断链 
		nextp = cur->next;
		//以头节点为开头开始对链表遍历 
		pre = L;
		//遍历头部节点，寻找待排序元素的前驱节点 
		while(pre->next && pre->next->data <= cur->data) pre = pre->next;
		//待排元素指向后继链表 
		cur->next = pre->next;
		//前驱节点指向当前节点 
		pre->next = cur;
		//当前节点指向原无序链表的后继节点，继续遍历 
		cur = nextp;
	} 
} 

题目： 设在一个带表头结点的单链表中所有元素结点的数据值无序， 试编写一个函数， 删除表中所有介于给定的两个值（ 作为函数参数给出） 之间的元素的元素（ 若存在).

思路：与第二题类似，只不过条件有变

代码：

//删除界定值
void deletebetweenmandn(int m,int n,LinkList &L){
	//初始化节点 a为暂存节点 p指向首个有元素的节点 pre保存前驱 
	LNode *a,*p = L->next,*pre=L;
	//遍历链表 
	while(p){
		//如果匹配值 
		if(m < p->data && p->data next;
			//前驱指向p的后继 
			pre->next = p;
			//释放当前节点 
			free(a);
		}else{
			//前驱更新 
			pre = p;
			//节点指向更新 
			p=p->next;
		}
	}
} 

题目：给定两个单链表， 编写算法找出两个链表的公共结点。

思路：计算两个链表的长度，相减后将两个链表指针移动到同一位置，判断哪个节点一致。即为公共节点。（因为公共节点后面元素一致，仅需用距离移动长链表即可）

代码：

//公共节点寻找
LinkList serachpublicnode(LinkList L,LinkList S){
	//遍历计算长度,寻找最长的链表 
	int lengthl=0,lengths=0; 
	//遍历计算L的长度 
	while(L){
		lengthl++;
		L = L->next;
	} 
	//遍历计算S的长度 
	while(S){
		lengths++;
		S = S->next;
	}
	//初始化距离长度 
	int distance = 0;
	//初始化长链表短链表 
	LinkList  longList,shortList;
	//找到最长的那条链表并计算距离 
	if(lengthl > lengths){
		//赋值 *** 作 
		longList = L->next;
		shortList = S->next; 
	    distance = lengthl - lengths; 
	}else{
		//赋值 *** 作 
		longList = S->next;
		shortList = L->next; 
		distance = lengths - lengthl; 
	}
	//遍历最长表，使最长表剩余的长度与最短表保持一致 
	while(distance>0){
		longList = longList->next;
		distance--;
	}
	//用最长表遍历 
	while(longList){
		//相等返回 
		if(longList == shortList){ 
			return longList;
			break; 
		}
		//继续迭代 
		longList = longList->next;
		shortList = shortList->next;
	}
	//未找到返回空 
	return NULL;
} 

题目：给定一个带表头结点的单链表，设head 为头指针，结点结构为(data,next) ，data为整型元素，next 为指针，试写出算法：按递增次序输出单表中各结点的数据元素，并释放结点所占的存储空间（ 要求： 不允许使用数组作为辅助空间）

思路：每次寻找链表里的最小值，然后输出后删除即可。

代码：

//递增输出结点元素，并释放空间
void sortlistandfree(LinkList &L){
	//初始化前驱节点 暂存节点 工作节点 
	LNode *pre,*r,*p;
	//遍历L 
	while(L){
		//保存前驱为头节点 
		pre = L;
		//p指向第一个元素 
		p = pre->next;
		//对第一个元素向后遍历 
		while(p->next){
			//如果找到最小值，更新前驱 
			if(p->next->data < pre->next->data)pre=p;
			//p后移 
			p = p->next;
		}
		//打印该删除的节点 
		printf("%d",pre->next->data);
		//r暂存删除节点 
		r = pre->next;
		//前驱next后移 
		pre->next = r->next;
		//释放节点 
		free(r);
	} 
	//释放头节点 
	free(L);
} 

题目： 将一个带头结点的单链表，分解为两个带头结点的单链表A和B ，使得A表中含有原表中序号为奇数的元素， 而B表中含有原表中序号为偶数的元素， 且保持其相对顺序不变。

思路：遍历链表，将大链表设置为A，新建链表B，将偶数元素塞入其中并从A里删除。

代码：

//A,B分表，奇偶分装
//这里取返回的表为B表，传入的表为A表 
LinkList dividelinklist(LinkList &L){
	//初始化b链表 
	LinkList b = (LinkList)malloc(sizeof(LNode));
	//b元素和指针都设置为空 
	b->data = -1;
	b->next = NULL;
	//i保存序号 
	int i = 1;
	//初始化 pre保存前指针。p为当前节点，a为暂存节点。r为尾插指向节点 
	LNode *pre = L,*p=L->next,*a,*r=b; 
	while(p){
		if(i%2==0){
		   //删除 *** 作，类似上面删除指定节点的代码
		    a = p;
		    //p后移 
		    p = p->next;
		    //A表中删除p节点 
		    pre->next = p;
		    //尾插插入B表
			a->next = NULL;
			//前驱的下一个节点链上当前节点 
			r->next = a;
			//前驱后移 
			r = a;
		}else{
			//前驱更新 
			pre = p;
			//节点后移 
			p = p->next;
		}
		//i自加 
		i++;
	}
	//返回B链头节点 
	return b;
} 

题目：设C= { a1,b1,a2,b2.....an,bn}为线性表，采用带头节点的hc单链表存放，设计一个就地算法拆分为两个线性表。使A={a1,a2...an},B={bn,...b1}。

思路：注意看这里的B倒置了，所以使用头插法插入节点即可，其余与上一题一致。

代码：

//线性表拆分
//这里很明显b表被倒置了，采用头插法即可！ 
LinkList speratetwolist(LinkList &L){
	//初始化b链表 
	LinkList b = (LinkList)malloc(sizeof(LNode));
	//b元素和指针都设置为空 
	b->data = -1;
	b->next = NULL;
	//i保存序号 
	int i = 1;
	//初始化 pre保存前指针。p为当前节点，a为暂存节点。r为尾插指向节点 
	LNode *pre = L,*p=L->next,*a,*r=b; 
	while(p){
		if(i%2==0){
		   //删除 *** 作，类似上面删除指定节点的代码
		    a = p;
		    //p后移 
		    p = p->next;
		    //A表中删除p节点 
		    pre->next = p;
		    //头插插入B表，a指向头节点后继 
			a->next = b->next;
			//头节点指向更新 
			b->next = a;
		}else{
			//前驱更新 
			pre = p;
			//节点后移 
			p = p->next;
		}
		//i自加 
		i++;
	}
	//返回B链头节点 
	return b;
} 

题目：在一个递增有序的线性表中， 有数值相同的元素存在·。若存储方式为单链表，设计算法去掉数值相同的元素， 使表中不再有重复的元素， 例如（ 7 ， 10 ， 10 ， 21 ， 30 ， 42 ， 42，42 ， 51 ， 70 ） ，将变为（ 7 ， 10 ， 21 ， 30 ， 42 ，51，70）。

思路：快慢指针 *** 作，类似顺序表里的替换，只不过这里的节点要保存释放。

代码：

//去除相同元素，快慢指针问题
void removesamenode(LinkList &L){
	//初始化节点 a指向第一个元素 b指向第二个元素 r暂存 pre保存前驱 
	LNode *a = L->next,*b = a->next,*r,*pre;
    //遍历开始 
	while(a && b){
		//如果元素不相等 
		if(a->data!=b->data){
			//保存慢节点指针 
			pre = a;
			//a前移 
			a = a->next;
			//b前移 
			b = b->next;
		}else{
			//r暂存a 
			r = a;
			//a前移 
			a=a->next;
			//前驱更新 
			pre->next = a;
			//释放r 
			free(r);
			//b前移 
			b = b->next;
		}
	}
} 

以上代码仅供参考，如有错误请指正！