2.3.3 单链表应用举例
【例2.3】 利用单链表的基本运算，求A-B。即若单链表B中的元素出现在单链表A中，则从A中删除该元素。
【分析】对于单链表A中的每个元素e，在单链表B中进行查找，如果在B中存在与A中相同的元素，则将元素从A中删除。
算法描述如下：
测试程序如下：
程序的运行结果如图2.18所示。
在具体实现算法A-B时，利用p=Get（B,i）依次取出单链表B中的元素，然后通过pos=LocatePos（A,p->data）在链表A中查找与该值相等的元素，并调用函数DeleteList（A,pos,&e）将A中对应的结点删除。
图2.18 程序运行结果
在该算法中，假设单链表A的长度为m，单链表B的长度为n，则时间主要耗费在A和B中对元素的查找上，算法的时间复杂度为O（m×n）。
上面的算法是通过单链表的基本运算实现的，也可以不用单链表的基本运算实现该算法。
上面算法中，在单链表A中，指针p指向单链表A中与单链表B中要比较的结点，pre指向p的前驱结点，在单链表B中，利用指针q指向B中的第一个结点，依次与A中p指向的结点的元素比较。如图2.19所示。
图2.19 初始时，p指向第一个要比较的结点
如果当前A中要比较的是元素ai，指针p指向ai所在结点，在B中，如果q指向元素bj所在结点，而bj=ai，则指针q停止向前比较。在A中，利用指针r指向要删除的结点p，令pre指向p的后继结点，从而使p指向的结点与链表断开，即r=p，pre->next=p->next。如图2.20所示。
图2.20 将A中要删除的结点与链表断开
然后，p指向链表A中下一个要比较的结点，最后释放r指向的结点。如图2.21所示。
图2.21 p指向下一个要比较的结点，同时释放r指向的结点
算法DelElem2的时间复杂度也是O（m×n）。
说明：在算法DelElem2的实现过程中，隐藏了查找元素结点与删除元素结点的实现细节，而在算法DelElem2中，将整个查找过程和删除过程展现得淋漓尽致。
【考研真题】假设一个带有表头结点的单链表，结点结构如下。
假设该链表只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点数据域的值，并返回1；否则返回0。要求如下。
（1）描述算法的基本设计思想。
（2）描述算法的详细实现步骤。
（3）根据设计思想和实现步骤，采用程序设计语言描述算法。
【分析】这是一道考研试题，主要考察对链表的掌握程度，这个题目比较灵活，利用一般的思维方式不容易实现。
（1）算法的基本思想：定义两个指针p和q，初始时均指向头结点的下一个结点。p指针沿着链表移动，当p指针移动到第k个结点时，q指针与p指针同步移动；当p指针移动到链表表尾结点时，q指针所指向的结点即为倒数第k个结点。
（2）算法的详细步骤如下。
①令count=0，p和q指向链表的第一个结点。
②若p为空，则转向⑤执行。
③若count等于k，则q指向下一个结点；否则令count++。
④令p指向下一个结点，转向②执行。
⑤若count等于k，则查找成功，输出结点的数据域的值，并返回1；否则，查找失败，返回0。
（3）算法实现代码如下。
