1.假设有两个按元素值递增有序排列的线性表a和b，均以单链表作为存储结构，请编写算法将a表和b表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表c，并要求利用原表（即a表和b表）的结点空间构造c表。

算法步骤如下：

1. 定义三个指针p、q、r，分别指向a表、b表、c表的当前结点；
2. 比较p、q指向的元素值，将较小的元素插入到c表的头部，并将指针后移；
3. 如果p或q指向的元素已经遍历完，则将另一个表中剩余的元素依次插入到c表的头部；
4. 最后将c表逆序，即得到按元素值递减有序排列的线性表c。

具体实现代码如下：

void mergeList(LinkList &a, LinkList &b, LinkList &c) {
// 初始化指针
LinkList p = a->next, q = b->next, r;
// 构造c表的头结点
c = a;
c->next = NULL;
// 循环比较a表和b表的元素值
while (p != NULL && q != NULL) {
if (p->data <= q->data) {
r = p;
p = p->next;
} else {
r = q;
q = q->next;
}
// 将较小的元素插入到c表的头部
r->next = c->next;
c->next = r;
}
// 将剩余的元素插入到c表的头部
while (p != NULL) {
r = p;
p = p->next;
r->next = c->next;
c->next = r;
}
while (q != NULL) {
r = q;
q = q->next;
r->next = c->next;
c->next = r;
}
// 将c表逆序
LinkList pre = NULL, cur = c->next, nxt;
while (cur != NULL) {
nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
c->next = pre;
}