【趣学C语言和数据结构100例】
问题描述
-
在带头结点的单链表中，删除所有值为 x 的结点，并释放其空间，假设值为 x 的结点不唯一，试编写算法以实现上述操作。
-
试编写在带头结点的单链表中寻找一个最小值结点的高效算法（假设该结点唯一）
-
设在一个带表头结点的单链表中，所有结点的元素值无序，试编写一个函数，删除表中所有介于给定的两个值（作为函数参数给出）之间的元素（若存在）。
-
给定两个单链表，试分析找出两个链表的公共结点。（暴力破解，最优解）
-
设 C={a1, b1, a2, b2, …, an, bn} 为线性表，采用带头结点的单链表存放，设计一个就地算法将其拆分为两个线性表，使得 A={a1, a2, …, an}, B={b1, b2, …, bn}。
代码分析
41.带头结点的单链表删指定值
//如果带头结点,则已经定义好L的头结点，可以直接使用L，L->next
Lnode *pre=L,*p=L->next
//如果不带头结点,则需要先定义L的结点
L=(Node *) malloc(sizeof (LNode));
L->next=NULL;
分析：无返回值+对链表操作+传入删除值，故函数命名为void 函数命(LiukList &L,int x)，使用while循环，条件为p ！=NULL（不到最后一直遍历），如果p的值为指定的x，则使pre的next和当前的p的next连接，即跳过p，并且释放p，使用free§，使p=pre->next;继续，如果p的值不为指定的x，则pre和p都向后移动一位，使用p=p->next
//如果遍历，则while循环，条件为p != NULL
while(p){
}
42.带头结点的单链表找一个最小值结点
分析：设置工作指针和存储的最小指针。工作指针：通常为Lnode *pre=L,*p=L->next，使用while§循环遍历，如果当前的工作指针的值<最小指针的值，则继续替换存储，然后继续都向后移动一位。到结束输出最小的值。
43.带表头结点的单链表删除指定范围的值
分析：可以参考41，只需要把p的值为指定的x改为范围，其余一样。
44.两个单链表找公共结点（暴力破解，最优解）
有两个链表：abcde和fgde,如下图
a->b->c
↘
d->e
↗
f->g
解法1（暴力破解）：
分析返回值为Lnode *类型，则函数名为Lnode * 函数名(LiiukList L1,LiiukList L2),分析进入函数后需要访问两个链表的工作指针p和q,初始化为Lnode * p=L1->next;使用while（p）循环遍历，使用while（q）循环继续内部遍历，如果p==q则返回p为公共结点，否则使q->向后移动，内部遍历后，没有找到结果，则外部循环移动，并且内部遍历从头遍历。到最后如果没有找到，则返回为NULL
解法2（最优解）：
//链表的长度
int length=0;
while(p){
lenth++;
p=p->next;
}
分析：计算两个的长度，从他们的相差的位置开始。注意：计算链表的长度后使p和q指向L->next。使长度大的先移动差位。然后使用while遍历访问，此时可以同时移动到他们相等时，即可找到公共结点。到最后如果没有找到，则返回为NULL
解法1（暴力破解）的时间复杂度为O(m*n) //平方级
解法2（最优解）的时间复杂度为O(m+n+min(m,n)) //常量级
45.链表的拆分
// 创建链表
LiukList L =