要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：
// 顺序表结构定义同上题
void ReverseList
}
2. 链表：
分析：
可以用交换数据的方式来达到逆置的目的。但是由于是单链表，数据的存取不是随机的，因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下：
当链表为空表或只有一个结点时，该链表的逆置链表与原表相同。
当链表含2个以上结点时，可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表。然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的：
结点结构定义如下：
typedef char DataType; //假设结点的数据域类型的字符
typedef struct nodeListNode;
typedef ListNode LinkList;
ListNode
LinkList head;
LinkList ReverseList
return head;
}
return head; //如是空表或单结点表，直接返回head
}
2.9 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。
答：
因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。
在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。
算法如下：
//顺序表存储结构如题2.7
void InsertIncreaseList
2.10 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。
答：
与上题相类似，只要从终端结点开始往前找到第一个比x大的结点数据，在这个位置插入就可以了。（边寻找，边移动）算法如下：
void InsertDecreaseList
2.11 写一算法在单链表上实现线性表的ListLength运算。
解：
由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下：
int ListLength
return len;
}
2.12 已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。
解：
分析：
由于要进行的是两单链表的连接，所以应找到放在前面的那张表的表尾结点，再将后表的开始结点链接到前表的终端结点后即可。该算法的主要时间消耗是用在寻找第一张表的终端尾结点上。这两张单链表的连接顺序无要求，并且已知两表的表长，则为了提高算法效率，可选表长小的单链表在前的方式连接。
具体算法如下：
LinkList Link
else
p=s;
while p=p-next; //查找短表终端结点
p-next = q; //将长表的开始结点链接在短表终端结点后
return s;
}
本算法的主要操作时间花费在查找短表的终端结点上，所以本算的法时间复杂度为：
O)
2.13 设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O，请分析算法的时间复杂度。
解：
根据已知条件，A和B是两个递增有序表，所以可以先取A表的表头建立空的C表。然后同时扫描A表和B表，将两表中最大的结点从对应表中摘下，并作为开始结点插入C表中。如此反复，直到A表或B表为空。最后将不为空的A表或B表中的结点依次摘下并作为开始结点插入C表中。这时，得到的C表就是由A表和B表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O。
算法如下：
LinkList MergeSort
else
