大一萌新小白解法

解题思路:创建-合并两个链表 - 归并排序即可

注意事项 记得释放内存。

参考代码:

#include <stdio.h>

#include <stdlib.h>

typedef struct ListNode {

    int id; 

    int score; 

    struct ListNode*next; 

} Node,*Lnode; 

Lnode createNode(int num)

{

    Lnode h = (Node*)malloc(sizeof(Node)); 

    h->next=NULL; 

    Lnode r=h; 

    int i;

    for(i=0; i<num; i++)

    {

        int x,y;

        scanf("%d %d",&x,&y);

        Node*s=(Lnode)malloc(sizeof(Node)); 

        s->id=x; 

        s->score=y; 

        r->next=s; 

        r=s; 

    }

    r->next=NULL; 

    return h; 

}

   Node* findMiddle(Node* head) {

    if (head == NULL || head->next == NULL) {

        return head;

    }

    Node* slow = head;

    Node* fast = head->next;

    while (fast != NULL && fast->next != NULL) {

        slow = slow->next;

        fast = fast->next->next;

    }

    return slow;

}

Node*mergeTwoLists(Node*head1,Node*head2) {

    if(head1 == NULL || head2 == NULL) { 

        return head1 == NULL ? head2 : head1;

    }

    Node*head = head1 ->id <= head2->id ? head1 : head2;

    Node*cur1 = head ->next;

    Node*cur2 = head == head1 ? head2 : head1;

    Node*pre = head; 

    while (cur1 != NULL && cur2 != NULL) { 

        if (cur1->id <= cur2->id) { 

            pre->next = cur1;

            cur1 = cur1->next; 

        } else { 

            pre->next = cur2;

            cur2 = cur2->next; 

        }

        pre = pre->next; 

    }

    pre->next = cur1 != NULL ? cur1 : cur2; 

    return head; 

}

Node* mergeSort(Node* head) {

    if (head == NULL || head->next == NULL) {

        return head;

    }

    Node* mid = findMiddle(head);

    Node* right = mid->next;

    mid->next = NULL;

    Node* left = head;

    left = mergeSort(left);

    right = mergeSort(right);

    head = mergeTwoLists(left, right);

    return head;

}

void printList(Lnode head) {

    Node *cur = head; 

    while (cur != NULL) { 

        printf("%d %d\n",cur->id,cur->score); 

        cur = cur->next;

    }

}

void freeList(Lnode head) {

    Node *cur = head; 

    Node *next = NULL; 

    while (cur != NULL) { 

        next = cur->next; 

        free(cur); 

        cur = next; 

    }

}

int main() {

    int m,n;

    scanf("%d %d",&m,&n);

    Lnode h1 = createNode(m); 

    Lnode h2 = createNode(n); 

    Lnode head = mergeSort(mergeTwoLists(h1->next, h2->next)); 

    printList(head);  

    freeList(head);

    return 0; 

}