1.2 链式存储结构的存储结构和实现

　　习题5分析：
　　单链表的逆置，即将原来的最后一个节点变成第一个节点，原来倒数第二个节点变成第二个节点，依此类推。
　　这里采用的方法是：从头到尾扫描单链表L，将头节点的next域置为NULL，将第一个元素节点插入头节点之后；再将第二个元素节点也插入头节点之后……依此类推。也就是将原链表的每个元素节点依次插入头节点之后，就可以完成单链表的逆置操作。其算法如下：

　　习题6分析：
　　本题的重点在于合并单链表时需要利用原有的存储空间，即要将原有链表的节点按元素值递增的顺序插入新链表中。因此，其算法思想为：按从小到大的顺序依次把LA和LB的元素插入新表的LC的末尾，最后还要处理LA或LB的剩余元素。其算法步骤如下：
　　（1）分别从链表头遍历LA和LB，如果LA和LB均未遍历完毕，执行步骤（2），否则执行步骤（3）。
　　（2）比较LA和LB的当前遍历值，将相对小的值所在的节点移动为LC的尾节点。
　　（3）将未遍历完毕的链表直接接入到LC的尾部。
　　其算法如下：

　　作为对本题的扩展，若将表LA和LB合并到表LC中时，要求LC递减有序而非递增有序时，应该如何处理呢？请读者自己思考并写出相应的算法。
　　习题7分析：
　　此题只需要对链表做一次遍历，并依次比较当前元素和下一元素的值，即可得到最终的链表。其算法步骤如下：
　　（1）从线性表L表头开始，循环执行步骤（2）和步骤（3），遍历到链表尾结束。
　　（2）如果当前节点元素与下一个节点元素值相同，则删除后一个节点。
　　（3）如果当前节点元素与下一个节点元素值不同，则遍历下一个节点。
　　具体算法如下：

　　习题8分析：
　　解答本题的重点在于理解题意。依据题意，该链表的结构如下：

　　链表建立完成后，其头指针为h，尾指针为e。对其中的一个p指向的节点，假设其前驱节点指针为pre，其后续节点指针为next，那么有：p->link=pre next。也就是说，当p和其前驱节点指针pre已知时，可以计算出p的后续节点指针：
　　pre p->link=pre （pre next）=（pre pre） next=next
　　即next=pre p->link。
　　这说明，第三个节点的指针是通过第一个节点的指针与第二个节点的link域“异或”运算得到的。
　　同样，当p和其后续节点next已知时，可以计算出p的前驱节点pre：
　　p->link next=（pre next） next=pre （next next）=pre
　　即pre=p->link next。
　　同样说明第一个节点指针是通过第二个节点的link域与第三个节点指针“异或”运算得到的。
　　根据这个基本原理，可得出本题的算法如下：

　　作为对本题的扩展，在本题数据结构的基础上，如何编写在第i个节点前插入一个节点以及删除第i个节点的算法呢？请读者自己思考并写出相应的算法。
　　3．训练自测表（如表1-4所示）

表1-4 应用题练习自测表