设计一段C语言算法,将两个非递减的有序链表合并为一个非递增的有序链表。要求结果 链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表 中允许有重复的数据。
时间: 2023-04-01 16:02:30 浏览: 98
可以使用双指针法,从两个链表的头部开始比较,将较小的节点插入到新链表的头部,直到其中一个链表为空。然后将剩余的节点直接插入到新链表的头部即可。
具体实现如下:
void mergeList(Node* list1, Node* list2) {
Node* p1 = list1;
Node* p2 = list2;
Node* head = NULL;
// 比较两个链表的节点,将较小的节点插入到新链表的头部
while (p1 != NULL && p2 != NULL) {
if (p1->data <= p2->data) {
Node* tmp = p1->next;
p1->next = head;
head = p1;
p1 = tmp;
} else {
Node* tmp = p2->next;
p2->next = head;
head = p2;
p2 = tmp;
}
}
// 将剩余的节点直接插入到新链表的头部
while (p1 != NULL) {
Node* tmp = p1->next;
p1->next = head;
head = p1;
p1 = tmp;
}
while (p2 != NULL) {
Node* tmp = p2->next;
p2->next = head;
head = p2;
p2 = tmp;
}
// 将新链表的头部赋值给原来的两个链表
*list1 = *list2 = *head;
}
阅读全文