题目

C语言代码实现

之前踩过一些坑，比如报错内存超过限制，需要注意不用的内存要释放。还报错显示超时，需要注意减少不必要的while循环，能精简要精简。

#include<stdio.h>
#include<stdlib.h>
#define max 10
//两个有序链表合并为一个有序链表，输入两行数，每行对应一个有序链表，以-1作为结束标志
typedef struct sqlist *list;
struct sqlist {
    int *elem;
    int length;
    int maxsize;
};

void initlist(list L) {
    L->elem = (int *)malloc(max * sizeof(int));
    L->length = 0;
    L->maxsize = max;
}

void addlist(list L, int num, int i) {
    //插入位置i是否正确
    if (i<1 || i>L->length+1) {
        printf("wrong position %d", i);
        return;
    }
    //L的空间是否充足
    if (L->length == L->maxsize) {
        L->elem = (int *)realloc(L->elem, (L->length + max) * sizeof(int));
        L->maxsize += max;
    }
    //i及其之后的数字后移
    for(int j=L->length; j>=i; j--) {
        L->elem[j] = L->elem[j-1];
    }
    //插入第i个位置，列表长度+1
    L->elem[i-1] = num;
    L->length++;
}

void print(list L) {
    for(int i=0; i<L->length; i++) {
        if (i==L->length-1) {
            printf("%d", L->elem[i]);
        } else {
            printf("%d ", L->elem[i]);
        }
    }
}

int main() {
    //分别创建两个有序链表，比大小，合并为一个有序链表，打印出来
    list a = (list)malloc(sizeof(list));
    list b = (list)malloc(sizeof(list));
    list c = (list)malloc(sizeof(list));
    initlist(a);
    initlist(b);
    initlist(c);
    int num;
    while (1)
    {
        scanf("%d", &num);
        if (num == -1) {
            break;
        }
        addlist(a, num, a->length+1);
    }

    while (1)
    {
        scanf("%d", &num);
        if (num == -1) {
            break;
        }
        addlist(b, num, b->length+1);
    }

    int i = 0;
    int j = 0;
    while(i<a->length || j<b->length) {
        if (i == a->length || b->elem[j] < a->elem[i]) {
            addlist(c, b->elem[j], c->length + 1);
            j++;
        } else {
            addlist(c, a->elem[i], c->length + 1);
            i++;
        } 
    }
    if (c->length == 0) {
        printf("NULL");
    } else {
        print(c);
    }
    return 0;
}