用C语言编写将两个多项式相加的函数，不能破坏输入数据，用一个链表实现，如果这两个多项式分别有M和N项，那么这个程序时间复杂度是多少?

在C语言中，可以使用链表结构来表示多项式的系数和指数，这样可以方便地处理任意长度的多项式。首先，我们需要定义一个节点结构来存储每一项的数据，然后创建一个链表来连接所有项。这里是一个简单的示例：

typedef struct {
    int coefficient;
    int exponent;
    struct node *next; // 指向下一个节点的指针
} PolynomialNode;

// 创建一个新的多项式项
PolynomialNode* createTerm(int coef, int exp) {
    PolynomialNode* newNode = (PolynomialNode*)malloc(sizeof(PolynomialNode));
    newNode->coefficient = coef;
    newNode->exponent = exp;
    newNode->next = NULL;
    return newNode;
}

// 将两个多项式相加
void addPolynomials(PolynomialNode** poly1, PolynomialNode** poly2, PolynomialNode** result) {
    PolynomialNode* current1 = *poly1;
    PolynomialNode* current2 = *poly2;
    PolynomialNode* currentResult = NULL;
    
    while (current1 != NULL || current2 != NULL) {
        if (current1 != NULL && (current2 == NULL || current1->exponent < current2->exponent)) {
            PolynomialNode* temp = current1;
            current1 = current1->next;
            free(temp);
            currentResult = insertCoefficient(currentResult, temp->coefficient, temp->exponent);
        } else if (current2 != NULL && (current1 == NULL || current1->exponent > current2->exponent)) {
            PolynomialNode* temp = current2;
            current2 = current2->next;
            free(temp);
            currentResult = insertCoefficient(currentResult, temp->coefficient, temp->exponent);
        } else { // 如果两项的指数相同，直接累加系数
            currentResult = insertCoefficient(currentResult, current1->coefficient + current2->coefficient, current1->exponent);
            current1 = current1->next;
            current2 = current2->next;
        }
    }

    *result = currentResult;
}

// 插入新项到链表
PolynomialNode* insertCoefficient(PolynomialNode* list, int coef, int exp) {
    if (list == NULL) {
        return createTerm(coef, exp);
    }
    PolynomialNode* newNode = createTerm(coef, exp);
    newNode->next = list;
    return newNode;
}

在这个实现中，时间复杂度是O(M+N)，其中M和N分别是两个多项式项的数量，因为我们需要遍历每个多项式一次。空间复杂度取决于结果多项式的长度，最坏的情况下可能会与输入多项式的总长度相等。