数据结构有序链表合并运行超时

Question

#include<bits/stdc++.h>
using namespace std;
typedef struct _LNode{
    int num;
    struct _LNode *next;
}Lnode,*LinkList;
void init(LinkList &S);
void ListInsert(LinkList &S,int i,int num);
void merge(LinkList &S1,LinkList &S2,LinkList &S3);
void print(LinkList S);
int main(){
    int i,j,num;
    LinkList S1,S2,S3;
    init(S1);init(S2);init(S3);
    i=0;j=0;
    while((cin>>num)&&num!=-1){
        ListInsert(S1,++i,num);
    }
    while((cin>>num)&&num!=-1){
    ListInsert(S2,++j,num);
    }
    merge(S1,S2,S3);
    if(S3->next==NULL||S3==NULL){
        printf("NULL");
        return 0;
    }
    S3=S3->next;
    int first=1;    
    while(S3!=NULL){
        if(first==1){
            cout<<S3->num;
            first=0;
        }
        else{
                cout<<" "<<(S3->num);
        }
        S3=S3->next;
    }
}
void init(LinkList &S){
    S=new Lnode;
    S->next=NULL;
}
void ListInsert(LinkList &S,int i,int num){
    Lnode *p=S;
    int j=0;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL||j>i-1){
        exit(0);
    }
    Lnode *q=new Lnode;
    q->next=p->next;
    p->next=q;
    q->num=num;
}
void merge(LinkList &S1,LinkList &S2,LinkList &S3){
    Lnode *p1=S1->next;
    Lnode *p2=S2->next;
    Lnode *p3;
    S3=p3=S1;
    while(p1!=NULL && p2!=NULL){
        if(p1->num < p2->num){
            p3->next=p1;
            p3=p1;
            p1=p1->next;
        }
        else{
            p3->next=p2;
            p3=p2;
            p2=p2->next;
        }
    }
    p3->next=p1?p1:p2;
    delete S2;
}

Answer 1

超时可能和16 17 19 20 行的L1 L2 两链表生成相关。