c++代码 已有a、b两个链表,每个链表中的结点包括学号、成绩。要求把两个链表合并,按学号升序排列
时间: 2023-06-06 12:04:17 浏览: 154
可以使用归并排序的思路,将两个链表合并并排序。具体实现如下:
1. 定义一个新链表,以及三个指针:一个指向新链表的头结点,两个分别指向两个原链表的头结点。
2. 判断两个原链表的头结点的学号大小,将较小的那个插入到新链表的末尾,同时将指向该节点的指针后移。
3. 重复步骤2,直到有一个链表遍历完,将另一个链表剩下的结点插入到新链表的末尾。
4. 返回新链表的头节点即可。
以下是示例代码:
struct ListNode {
int id;
int score;
ListNode* next;
ListNode(int id, int score) : id(id), score(score), next(nullptr) {}
};
ListNode* mergeLists(ListNode* head1, ListNode* head2) {
ListNode* dummy = new ListNode(-1, -1); // 定义新链表的头结点
ListNode* cur = dummy; // 指向新链表的末尾
ListNode* p1 = head1; // 指向第一个原链表的头结点
ListNode* p2 = head2; // 指向第二个原链表的头结点
while (p1 && p2) { // 两个链表都还有元素
if (p1->id < p2->id) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
cur = cur->next;
}
// 如果有一个链表遍历完了,将另一个链表剩余的结点插入到新链表的末尾
if (p1) cur->next = p1;
if (p2) cur->next = p2;
return dummy->next; // 返回新链表的头结点
}
阅读全文