解题思路:创建-合并两个链表 - 归并排序即可
注意事项 记得释放内存。
参考代码:
#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;
}
0.0分
0 人评分
众数问题 (C语言代码)浏览:3532 |
C语言程序设计教程(第三版)课后习题6.5 (Java代码)浏览:1159 |
校门外的树 (C语言代码)浏览:721 |
C语言程序设计教程(第三版)课后习题12.1 (C语言代码)浏览:997 |
简单的a+b (C语言代码)浏览:751 |
C语言程序设计教程(第三版)课后习题8.9 (Java代码)浏览:1345 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:998 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:943 |
C语言程序设计教程(第三版)课后习题6.8 (C++代码)浏览:599 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:861 |