板子：合并两个有序链表
和数组合并是同一个骨架：两个指针比较，小的那个接到结果表尾部。区别是链表不需要新空间：直接把原来的结点挂过去；最后剩下的一整段，改一个指针就接上了。
代码
void mergeList(LinkList A, LinkList B) { // 两个升序链表合并到 A，结果升序，不申请新结点
LNode *p = A->next, *q = B->next, *r = A; // r 指向结果表的表尾
while (p != NULL && q != NULL) { // 两边都还有结点才需要比较
if (p->data <= q->data) { r->next = p; r = p; p = p->next; } // <=：相等先取 A，稳定
else { r->next = q; r = q; q = q->next; }
}
r->next = (p != NULL) ? p : q; // 剩下的那段整体接上，不用一个个挂
free(B); // B 的头结点用不到了
}
void mergeDesc(LinkList A, LinkList B) { // 两个升序链表合并成降序：每次把较小的头插到 A
LNode *p = A->next, *q = B->next, *s;
A->next = NULL; // A 的头结点先断开，当成空表
while (p != NULL || q != NULL) { // 注意是 ||：剩下的结点也要一个个头插
if (q == NULL || (p != NULL && p->data <= q->data)) { s = p; p = p->next; } // B 取完了或 p 更小：取 p
else { s = q; q = q->next; }
s->next = A->next; // 头插：先插的（小的）会被挤到后面
A->next = s;
}
free(B);
}复杂度：时间
两种合并怎么选
| 要的结果 | 做法 | 剩下的结点 |
|---|---|---|
| 升序（和原来同序） | 尾插 | 整段一次接上 |
| 降序（和原来反序，王道 2.3 综合题） | 头插 | 必须逐个头插，否则顺序不对 |
易错点
- 升序合并的收尾只要一句
r->next = p ? p : q，不用写两个while。这是链表比数组省事的地方。 - 降序合并的循环条件是
||，判断「取p」时要先检查q == NULL，否则会访问空指针。 r的初值是头结点A，不是A->next。- 求两个有序链表的交集也是这个骨架：值相等时保留，否则小的一方后移并释放掉被跳过的结点。