运行超时，是main函数里的循环调用了太多次函数吗

Question

已知两个非降序链表序列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
时间限制
1500 ms
内存限制
128 MB

#include <iostream>
using namespace std;
typedef struct Lnode
{
    int data;
    struct Lnode *next;
} Lnode, *Linklist;

int creat(Linklist &L)
{
    L = new Lnode;
    L->next = NULL;
    Linklist p, q = L;
    while (1)
    {
        p = new Lnode;
        cin >> p->data;
        if (p->data == -1)
        {
            return 0;
        }
        p->next = NULL;
        q->next = p;
        q = p;
    }
}

void cmp(Linklist &L, int e)
{
    Linklist p = L;
    if ( p->next == NULL ||e < p->next->data )
    {
        Linklist q = new Lnode;
        q->data = e;
        q->next = p->next;
        p->next = q;
    }
    else
    {
        while ( p->next != NULL && e >= p->next->data)
        {
            p = p->next;
        }
        Linklist q = new Lnode;
        q->data = e;
        q->next = p->next;
        p->next = q;
    }
}
void Print(Linklist L)
{
    Linklist p = L->next;
    if ( p == NULL )
    {
        cout << "NULL";
    }
    while (p != NULL)
    {
        cout << p->data;
        if (p->next != NULL)
        {
            cout << " ";
        }
        p = p->next;
    }
}
int main()
{
    int t;
    Linklist L;
    creat(L);
    while (1)
    {
        cin >> t;
        if (t == -1)
        {
            break;
        }
        cmp(L, t);
    }
    Print(L);
    return 0;
}
 

Answer 1

有序链表合并比重新排序效率高

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

typedef struct Lnode {
    int val;
    struct Lnode *next;
} Lnode;

void input(Lnode *p) {
    int v;
    while (scanf("%d", &v), v != -1) {
        p->next = (Lnode*)malloc(sizeof(Lnode));
        p = p->next;
        p->val = v;
    }
    p->next = NULL;
}

int compare(Lnode *p, Lnode *q) {
    return p->val < q->val;
}

void pb(Lnode **t, Lnode **p) {
    (*t)->next = *p;
    *t = *p;
    *p = (*p)->next;
}

void merge(Lnode *h1, Lnode *h2) {
    Lnode h3, *p, *q, *t = &h3;
    for (p = h1->next, q = h2->next; p && q;) {
        if (compare(p, q)) {
            pb(&t, &p);
        } else {
            pb(&t, &q);
        }
    }
    while (p) {
        pb(&t, &p);
    }
    while (q) {
        pb(&t, &q);
    }
    t->next = NULL;
    h1->next = h3.next;
}

void output(Lnode *h) {
    h = h->next;
    if (h) {
        while (h->next) {
            printf("%d ", h->val);
            h = h->next;
        }
        printf("%d", h->val);
    }
}

int main() {
    Lnode h1, h2;
    input(&h1);
    input(&h2);
    merge(&h1, &h2);
    output(&h1);
    return 0;
}