怎么老是运行超时啊，怎么改啊

Question

1-4 两个有序链表序列的合并分数 85
全屏浏览题目
切换布局
作者 DS课程组
单位 浙江大学
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。
输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。
输出格式:
在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。
输入样例:
1 3 5 -1
2 4 6 8 10 -1
输出样例:
1 2 3 4 5 6 8 10

代码长度限制
16 KB
Python (python3)
时间限制
1500 ms
内存限制
256 MB
其他编译器
时间限制
1500 ms

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElementType;
typedef struct node {
    ElementType data;
    struct node *Next;
} *List;

// 创建链表
List CreateList(void) {
   int i;
    //int n=0;
    int val=0;
        List pHead = (List)malloc(sizeof(struct node));
        List pTail=pHead;
        pTail->Next=NULL;

        for(i=0;;i++)//输入数据
            {
                scanf("%d",&val);
                if(val<0){
                    break;
                }
              List pNew= (List)malloc(sizeof(struct node));
              pNew->data=val;
              pTail->Next=pNew;
              pNew->Next=NULL;
              pTail=pNew;}


        return pHead;


}


// 打印链表
void PrtList(List L) {
    List p = L->Next;
  int flag = 1;
    while(p)
    {
        if (flag)
            {
                flag = 0;
                printf("%d",p->data);
            }
            else
                printf(" %d",p->data);
            p = p->Next;
    }

    printf("\n");
}
void sort(List pHead){
   int t,i,j;
    int len=length_list(pHead);
    List p=NULL;
    List q=NULL;
    for(i=0,p=pHead->Next;i<len;p=p->Next,i++){
        for(j=i+1,q=p->Next;j<len;j++,q=q->Next){
            if(p->data>q->data){
                t=p->data;
                p->data=q->data;
                q->data=t;
            }
        }
    }


}
int length_list(List A){
    int i=0;
    List p=A->Next;
    while(p){
        i++;
        p=p->Next;
    }
    return i;
}

int main(void) {
    List A = CreateList();


    List B = CreateList();
    if(A->Next==NULL&&B->Next==NULL){
        printf("NULL");
    }
    else if(A->Next==NULL&&B->data!=NULL){
        sort(A);
    PrtList(A);
    }
    else if(B->Next==NULL&&A->data!=NULL){
        sort(B);
    PrtList(B);
    }

    // 找到链表A的最后一个节点
    else{
    List tmp = A;
    while (tmp->Next != NULL) {
        tmp = tmp->Next;
    }
    //  连接A和B，注意链表是带头结点的，连接时要忽略B的头结点，从第一个节点开始
    tmp->Next = B->Next;

    sort(A);
    PrtList(A);}
    return 0;
}

Answer 1

【以下回答由 GPT 生成】

对于优化排序链表程序的运行时间，我有以下几个建议：

1. 使用归并排序算法：在两个有序链表的合并过程中，可以使用归并排序算法，将两个有序链表合并为一个有序链表。归并排序的时间复杂度为O(nlogn)，相比于冒泡排序或插入排序，能够更快地排序链表。

2. 将链表元素存储在数组中：由于题目中允许链表长度最大为16KB，而链表的访问效率较低，可以考虑将链表元素存储在数组中，通过数组的随机访问特性来提高程序的运行速度。将链表元素复制到数组中，然后使用归并排序算法对数组进行排序，最后再将排序后的数组转换回链表。

3. 使用双指针法进行合并：在链表的合并过程中，可以使用双指针法来遍历两个链表。定义两个指针分别指向两个链表的头结点，比较两个指针指向的元素大小，将较小的元素加入到新的链表中，并将指针后移一位。重复上述步骤，直到其中一个链表为空。最后将非空链表剩余的部分加入到新的链表中。

下面是使用C语言实现上述优化方法的示例代码：

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct node {
    ElementType data;
    struct node *Next;
} *List;

// 创建链表
List CreateList(void) {
    int val;
    List pHead = (List)malloc(sizeof(struct node));
    List pTail = pHead;
    pTail->Next = NULL;

    while (scanf("%d", &val) && val >= 0) {
        List pNew = (List)malloc(sizeof(struct node));
        pNew->data = val;
        pTail->Next = pNew;
        pNew->Next = NULL;
        pTail = pNew;
    }

    return pHead;
}

// 打印链表
void PrtList(List L) {
    List p = L->Next;
    int flag = 1;

    while (p) {
        if (flag) {
            flag = 0;
            printf("%d", p->data);
        }
        else {
            printf(" %d", p->data);
        }
        p = p->Next;
    }

    printf("\n");
}

// 获取链表长度
int length_list(List L) {
    int length = 0;
    List p = L->Next;

    while (p) {
        length++;
        p = p->Next;
    }

    return length;
}

// 合并两个有序链表
List merge_lists(List L1, List L2) {
    List p1 = L1->Next;
    List p2 = L2->Next;
    List pHead = (List)malloc(sizeof(struct node));
    List pTail = pHead;
    pHead->Next = NULL;

    while (p1 && p2) {
        if (p1->data <= p2->data) {
            pTail->Next = p1;
            p1 = p1->Next;
        }
        else {
            pTail->Next = p2;
            p2 = p2->Next;
        }
        pTail = pTail->Next;
    }

    if (p1) {
        pTail->Next = p1;
    }
    if (p2) {
        pTail->Next = p2;
    }

    return pHead;
}

// 使用归并排序算法对链表进行排序
List sort(List pHead) {
    int len = length_list(pHead);
    if (len <= 1) {
        return pHead;
    }

    List p = pHead->Next;
    for (int i = 0; i < len / 2 - 1; i++) {
        p = p->Next;
    }
    List q = p->Next;
    p->Next = NULL;

    List L1 = sort(pHead);
    List L2 = sort(q);

    return merge_lists(L1, L2);
}

int main() {
    List L1, L2;
    L1 = CreateList();
    L2 = CreateList();

    List L3 = merge_lists(L1, L2);
    L3 = sort(L3);

    PrtList(L3);

    return 0;
}

以上就是优化排序链表程序的运行时间的具体解决方案。希望对你有所帮助！

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7797991

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^