数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
1
每日一练
1．已知两个单链表 A 和 B,其头指针分别为 heada 和 headb，编写一个过程从单链表 A 中删除自第 i 个元素起的共 len 个元素，然后将单链表 A 插入到单链表 B 的第 j 个元素之前。
类似本题的另外叙述有：
（1）h1、h2 为两个链表的表头指针，结点结构为 data 和 link 两个域组成。写出算法 inde(h1,h2,i,j,l),将链表 h1 从第 i 个结点起的 l 个结点删除，并插入到 h2 表的第 j 个结点之前。
正确答案
ps：||代表注释
1.[题目分析] 在单链表中删除自第i个元素起的共len个元素，应从第1个元素起开始计数，记到第i个时开始数len个，然后将第i-1个元素的后继指针指向第i+len个结点，实现了在A链表中删除自第i个起的len个结点。这时应继续查到A的尾结点，得到删除元素后的A链表。再查B链表的第j个元素，将A链表插入之。插入和删除中应注意前驱后继关系，不能使链表“断链”。另外，算法中应判断i，len和j的合法性。
LinkedList DelInsert（LinkedList heada ，headb， int i，j，len）
∥heada和headb均是带头结点的单链表。本算法删除heada链表中自第i个元素起的共len个元素，然后将单链表heada插入到headb的第j个元素之前。
{ if（i<1 || len<1 || j<1）{printf（“参数错误\n”）；exit（0）；}∥参数错，退出算法。
p=heada；∥p为链表A的工作指针，初始化为A的头指针，查到第i个元素时，p指向第i-1个元素
k=0；∥计数
while（p!=null && k<i-1）∥查找第i个结点。
{k++；p=p->next；}
if（p==null）{printf（“给的%d太大\n”,i）；exit（0）；} ∥i太大，退出算法
q=p->next；∥q为工作指针，初始指向A链表第一个被删结点。
k=0；
while（q!=null && k<len）{k++；u=q，q=q->next；free（u）；} ∥删除结点，后移指针。
if（k<len）{printf（“给的%d太大\n”,len）；exit（0）；}
p->next=q；∥A链表删除了len个元素。
if (heada->next!=null) ∥heada->next=null说明链表中结点均已删除，无需往B表插入
{ while（p->next!=null）p= p->next；∥找A的尾结点。
q=headb；∥q为链表B的工作指针。
k=0；∥计数
while（q!=null && k<j-1） ∥查找第j个结点。
{k++；q= q->next；} ∥查找成功时，q指向第j-1个结点
if（q==null）{printf（“给的%d太大\n”,j）；exit（0）；}
p->next=q->next； ∥将A链表链入
q->next=heada->next； ∥A的第一元素结点链在B的第j-1个结点之后
}// if
free（heada）；∥释放A表头结点。
}∥算法结束。
与本题类似的题的解答如下：
（1）本题与第14题基本相同，不同之处仅在于插入B链表第j个元素之前的，不是删除了len个元素的A链表，而是被删除的len个元素。按照上题，这len个元素结点中第一个结点的指针p->next，查找从第i个结点开始的第len个结点的算法修改为：
k=1；q=p->next； //q指向第一个被删除结点
while（q!=null && k<len） ∥查找成功时，q指向自i起的第len个结点。
{k++；q= q->next；}
if（k<len） {printf（“给的%d太大\n”,len）；exit（0）；}
转发朋友圈，点下“好看”就是对小编的最大帮助！
-end-