1.设A、B是两个单链表，其表中元素递增有序，写一算法将A、B归并成一个按照元素值 （1）递增; （2）递减 的有序单链表C.要求辅助空间为O(1).并分析算法的时间复杂度。生成C语言代码

为了合并两个递增有序的单链表A和B，并将其排序成一个新的递增或递减链表C，可以采用迭代的方式，同时利用两个指针分别遍历A和B。以下是基本的步骤：

1. **递增顺序合并**：
- 初始化空链表C和两个指针pA和pB，分别指向A和B的头结点。
- 比较pA和pB指向的节点值，选择较小的那个添加到链表C并移动相应的指针。
- 当其中一个链表为空时，将另一个链表剩余部分依次添加到C。
- 最后，将链表C的头结点设置为之前未遍历完的非空链表。

struct ListNode {
    int val;
    struct ListNode *next;
};

void mergeInOrder(struct ListNode* A, struct ListNode* B, struct ListNode** C) {
    struct ListNode dummy = {0, NULL};
    struct ListNode *tail = &dummy;
    while (A && B) {
        if (A->val <= B->val) {
            tail->next = A;
            A = A->next;
        } else {
            tail->next = B;
            B = B->next;
        }
        tail = tail->next;
    }
    if (A)
        tail->next = A;
    else
        tail->next = B;
    *C = dummy.next;
}

**递减顺序合并**：
- 步骤类似，只是比较节点值时取较大者。

时间复杂度分析：因为每个节点都会被访问一次，所以时间复杂度是O(M+N)，其中M和N分别是A和B的长度。