解题思路:创建-合并两个链表 - 归并排序即可
注意事项 记得释放内存。
参考代码:
#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语言程序设计教程(第三版)课后习题6.9 (C++代码)论pow函数的应用浏览:1037 |
【蟠桃记】 (C++代码)(递归计算)浏览:979 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:794 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:494 |
简单的a+b (C语言代码)浏览:652 |
川哥的吩咐 (C++代码)浏览:1031 |
奖学金 (C++代码)浏览:2021 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:662 |
C语言程序设计教程(第三版)课后习题9.1 (C语言代码)浏览:690 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:704 |