p->next=la->next；/*将p结点前插入头结点后。*/ la->next=p；p=r； }

}∥结束算法

（3）本题要求倒排循环链表，与上面倒排单链表处理不同之处有二：一是初始化成循环链表而不是空链表；二是判断链表尾不用空指针而用是否是链表头指针。算法中语句片段如下：

p=la->next； ∥p为工作指针。

la->next=la； ∥初始化成空循环链表。 while（p!=la） ∥当p=la时循环结束。 {r=p->next； ∥暂存p的后继结点 p->next=la->next；∥逆置 la->next=p； p=r； }

（4）不带头结点的单链表逆置比较复杂，解决方法可以给加上头结点：

la=（LinkedList）malloc（sizeof（node））； la->next=L；

之后进行如上面（2）那样的逆置，最后再删去头结点： L=la->next； ∥L是不带头结点的链表的指针。 free（la）； ∥释放头结点。

若不增加头结点，可用如下语句片段： p=L->next； ∥p为工作指针。

L->next=null；∥第一结点成为尾结点。 while（p!=null） {r=p->next；

p->next=L；∥将p结点插到L结点前面。

L=p； ∥L指向新的链表“第一”元素结点。 p=r； } （5）同（4），只是叙述有异。 （6）同（2），差别仅在于叙述不同。

22．[题目分析] 在无序的单链表上，查找最小值结点，要查遍整个链表，初始假定第一结点是最小值结点。当找到最小值结点后，判断数据域的值是否是奇数，若是，则“与其后继结点的值相交换”即仅仅交换数据域的值，用三个赋值语句即可交换。若与后继结点交换位置，则需交换指针，这时应知道最小值结点的前驱。至于删除后继结点，则通过修改最小值结点的指针域即可。

[算法设计]

void MiniValue（LinkedList la）

∥la是数据域为正整数且无序的单链表，本算法查找最小值结点且打印。若最小值结点的数值是奇数，则与后继结点值交换；否则，就删除其直接后继结点。

{p=la->next； ∥设la是头结点的头指针，p为工作指针。

pre=p； ∥pre指向最小值结点，初始假定首元结点值最小。 while（p->next!=null） ∥p->next是待比较的当前结点。 {if（p->next->datadata）pre=p->next；

p=p->next； ∥后移指针

}

printf（“最小值=%d\\n”，pre->data）； if（pre->data%2!=0） ∥处理奇数

if（pre->next!=null）∥若该结点没有后继，则不必交换

{t= pre->data；pre->data=pre->next->data；pre->next->data=t；}∥交换完毕

else∥处理偶数情况

if（pre->next!=null）∥若最小值结点是最后一个结点，则无后继 {u=pre->next；pre->next=u->next；free（u）；} ∥释放后继结点空间

23．[题目分析] 将一个结点数据域为字符的单链表，分解成含有字母字符、数字字符和其它字符的三个循环链表，首先要构造分别含有这三类字符的表头结点。然后从原链表第一个结点开始，根据结点数据域是字母字符、数字字符和其它字符而分别插入到三个链表之一的链表。注意不要因结点插入新建链表而使原链表断链。另外，题目并未要求链表有序，插入采用“前插法”，每次插入的结点均成为所插入链表的第一元素的结点即可。

void OneToThree（LinkedList L，la，ld，lo）

∥L是无头结点的单链表第一个结点的指针，链表中的数据域存放字符。本算法将链表L分解成含有英文字母字符、数字字符和其它字符的带头结点的三个循环链表。

{la=（LinkedList）malloc（sizeof（LNode））； ∥建立三个链表的头结点 ld=（LinkedList）malloc（sizeof（LNode））；

lo=（LinkedList）malloc（sizeof（LNode））；

la->next=la；ld->next=ld；lo->next=lo；∥置三个循环链表为空表 while（L!=null）∥分解原链表。

{r=L; L=L->next; ∥L指向待处理结点的后继

if（r->data>=‘a’&& r->data<=‘z’|| r->data>=‘A’&& r->data<=‘Z’） {r->next=la->next； la->next=r；} ∥处理字母字符。 else if（r->data>=‘0’&& r->data<=‘9’）

{r->next=ld->next；ld->next=r；} ∥处理数字字符 else {r->next=lo->next；lo->next=r；} ∥处理其它符号。

}∥结束while（L!=null）。

}∥算法结束

[算法讨论] 算法中对L链表中每个结点只处理一次，时间复杂度O（n），只增加了必须的三个表头结点，符合题目“用最少的时间和最少的空间”的要求。

24．[题目分析] 在递增有序的线性表中，删除数值相同的元素，要知道被删除元素结点的前驱结点。

LinkedList DelSame（LinkedList la）

∥la是递增有序的单链表，本算法去掉数值相同的元素，使表中不再有重复的元素。 {pre=la->next；∥pre是p所指向的前驱结点的指针。

p=pre->next；∥p是工作指针。设链表中至少有一个结点。 while（p!=null）

if（p->data==pre->data） ∥处理相同元素值的结点 {u=p；p=p->next；free（u）；} ∥释放相同元素值的结点

else {pre->next=p；pre=p；p=p->next；} ∥处理前驱，后继元素值不同 pre->next=p；∥置链表尾。 }∥DelSame