编写将两个带头结点的递增有序单链表l1和l2合并为一个非递减的有序单链表l1的算法 merge( linklist &l1, linklist &l2 )，要求直接使用原链表中的结点。

要编写一个合并两个递增有序链表 `L1` 和 `L2` 的算法，可以采用迭代或者递归的方式。这里我们提供一种迭代的解决方案： ```python struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ListNode* mergeTwoLists(ListNode* L1, ListNode* L2) { // 创建一个新的头节点作为结果链表 ListNode* head = new ListNode(0); ListNode* tail = head; while (L1 != NULL && L2 != NULL) { // 如果 L1 的值小于 L2 的值，将 L1 的元素添加到结果链表 if (L1->val <= L2->val) { tail->next = L1; L1 = L1->next; } else { // 否则，将 L2 的元素添加到结果链表 tail->next = L2; L2 = L2->next; } // 移动 tail 指针以便继续比较下一个节点 tail = tail->next; } // 如果其中一个链表还有剩余元素，直接将其添加到结果链表尾部 if (L1 != NULL) { tail->next = L1; } else { tail->next = L2; } return head->next; // 返回合并后的链表头节点 } ``` 在这个算法中，我们不断比较 `L1` 和 `L2` 的当前节点值，将较小的节点添加到新链表中，并更新指针。当有一个链表遍历完后，我们将另一个链表剩下的部分添加到结果链表的尾部。

可以采用双指针法，将两个链表从头开始比较大小，较小的节点接到新链表的头部，直到其中一个链表为空，然后将另外一个链表接到新链表的头部即可。 具体实现如下： ```c #include <stdio.h> #include <stdlib.h> typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 创建带头结点的单链表 LinkList createList(int n) { LinkList head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; LNode *tail = head; for (int i = 0; i < n; i++) { int data; scanf("%d", &data); LNode *node = (LNode*)malloc(sizeof(LNode)); node->data = data; node->next = NULL; tail->next = node; tail = node; } return head; } // 合并两个递增有序的带头结点的单链表 LinkList merge(LinkList A, LinkList B) { LinkList C = (LinkList)malloc(sizeof(LNode)); C->next = NULL; LNode *tail = C; LNode *p = A->next; LNode *q = B->next; while (p && q) { if (p->data <= q->data) { tail->next = p; p = p->next; } else { tail->next = q; q = q->next; } tail = tail->next; } if (p) { tail->next = p; } if (q) { tail->next = q; } // 翻转链表 LNode *pre = NULL; LNode *cur = C->next; while (cur) { LNode *next = cur->next; cur->next = pre; pre = cur; cur = next; } C->next = pre; return C; } // 打印链表 void printList(LinkList head) { LNode *p = head->next; while (p) { printf("%d ", p->data); p = p->next; } printf("\n"); } int main() { int m, n; printf("请输入链表A的长度："); scanf("%d", &m); printf("请按递增顺序依次输入链表A的%d个元素：", m); LinkList A = createList(m); printf("请输入链表B的长度："); scanf("%d", &n); printf("请按递增顺序依次输入链表B的%d个元素：", n); LinkList B = createList(n); LinkList C = merge(A, B); printf("合并后的递减有序的带头结点的单链表为："); printList(C); return 0; } ``` 时间复杂度为 O(m+n)，符合题目要求。