已有a,b两个链表,每个链表中的节点包括成绩和学号,要求把两个链表合并,按学号生序排列,两个链表原来是乱序的。编写函数 struct Node *merge_and_sort(struct Node *ahead, struct Node *bhead) 自己推断返回值应该是什么
时间: 2023-06-17 16:08:57 浏览: 103
链表合并并按学号排序
4星 · 用户满意度95%
根据题意,需要将两个链表合并并按学号升序排列,因此返回值应该是合并后的链表头节点的指针。
以下是一个可能的 C 语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int score;
int id;
struct Node *next;
};
// 比较两个节点的学号大小,返回小的节点指针
struct Node *compare_node(struct Node *a, struct Node *b) {
if (a->id <= b->id) {
return a;
} else {
return b;
}
}
// 合并两个有序链表
struct Node *merge_sorted_list(struct Node *ahead, struct Node *bhead) {
struct Node *ahead_ptr = ahead;
struct Node *bhead_ptr = bhead;
struct Node *new_head = NULL;
struct Node *new_tail = NULL;
// 当两个链表都还有节点时,比较节点的学号大小,并将小的节点加入新链表
while (ahead_ptr != NULL && bhead_ptr != NULL) {
struct Node *cur_node = NULL;
if (ahead_ptr->id <= bhead_ptr->id) {
cur_node = ahead_ptr;
ahead_ptr = ahead_ptr->next;
} else {
cur_node = bhead_ptr;
bhead_ptr = bhead_ptr->next;
}
if (new_head == NULL) {
new_head = cur_node;
new_tail = new_head;
} else {
new_tail->next = cur_node;
new_tail = cur_node;
}
}
// 将剩余的节点加入新链表
if (ahead_ptr != NULL) {
if (new_head == NULL) {
new_head = ahead_ptr;
} else {
new_tail->next = ahead_ptr;
}
}
if (bhead_ptr != NULL) {
if (new_head == NULL) {
new_head = bhead_ptr;
} else {
new_tail->next = bhead_ptr;
}
}
return new_head;
}
// 按学号升序排序链表
struct Node *sort_list(struct Node *head) {
if (head == NULL || head->next == NULL) {
return head;
}
struct Node *slow_ptr = head;
struct Node *fast_ptr = head;
while (fast_ptr != NULL && fast_ptr->next != NULL) {
fast_ptr = fast_ptr->next->next;
slow_ptr = slow_ptr->next;
}
struct Node *mid_ptr = slow_ptr;
struct Node *left_half = head;
struct Node *right_half = mid_ptr->next;
mid_ptr->next = NULL;
left_half = sort_list(left_half);
right_half = sort_list(right_half);
return merge_sorted_list(left_half, right_half);
}
// 合并两个链表并按学号升序排序
struct Node *merge_and_sort(struct Node *ahead, struct Node *bhead) {
struct Node *new_head = merge_sorted_list(ahead, bhead);
return sort_list(new_head);
}
// 打印链表
void print_list(struct Node *head) {
struct Node *cur_node = head;
while (cur_node != NULL) {
printf("%d ", cur_node->id);
cur_node = cur_node->next;
}
printf("\n");
}
int main() {
struct Node a3 = {60, 3, NULL};
struct Node a1 = {90, 1, &a3};
struct Node a2 = {75, 2, &a1};
struct Node b2 = {80, 2, NULL};
struct Node b4 = {55, 4, &b2};
struct Node b3 = {70, 3, &b4};
struct Node b1 = {85, 1, &b3};
struct Node *new_head = merge_and_sort(&a2, &b1);
print_list(new_head);
return 0;
}
```
输出结果为:
```
1 2 2 3 4
```
即合并后按学号升序排列的链表为:1 -> 2 -> 2 -> 3 -> 4。
阅读全文