[编程入门]链表合并

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
struct ListNode{
    int num;
    int score;
    ListNode* next;
};
void insertHead(ListNode* &L,int number,int mark){
    ListNode* newnode=new ListNode;
    newnode->num=number;
    newnode->score=mark;
    newnode->next=L;
    L=newnode;
}
void sortnode(ListNode* &L){
    if(!L || !L->next) return;
    bool swapped;
    do{
        swapped=false;
        ListNode* cur=L;
        while(cur && cur->next){
            if(cur->num > cur->next->num){
                swap(cur->num,cur->next->num);
                swap(cur->score,cur->next->score);
                swapped=true;
            }
            cur=cur->next;
        }
    }while(swapped);
}
ListNode* merge(ListNode* L1,ListNode* L2){
    ListNode* dummy=new ListNode;
    ListNode* P3=dummy;
    ListNode* P1=L1;
    ListNode* P2=L2;
    while(P1!=NULL && P2!=NULL){
        if(P1->score <= P2->score){
            P3->next=P1;
            P1=P1->next;
        }else{
            P3->next=P2;
            P2=P2->next;
        }
        P3=P3->next;
    }
    P3->next=P1==NULL?P2:P1;
    return dummy->next;
}
void printList(ListNode* L){
    ListNode* cur=L;
    while(cur!=NULL){
        cout<<cur->num<<" "<<cur->score<<endl;
        cur=cur->next;
    }
}
int main()
{
    //头插法插入
    int n,m,number,mark;
    cin>>n>>m;
    ListNode* L1=NULL;
    ListNode* L2=NULL;
    for(int i=0;i<n;i++){
        cin>>number>>mark;
        insertHead(L1,number,mark);
    }
    sortnode(L1);
    for(int i=0;i<m;i++){
        cin>>number>>mark;
        insertHead(L2,number,mark);
    }
    sortnode(L2);
    //hebing 
    ListNode* L3=NULL;
    L3=merge(L1,L2);
    //print
    printList(L3);
    return 0;
}