请设计一个算法并编程实现:将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。要使用c语言要求自己插入数字链表
时间: 2024-11-18 10:18:19 浏览: 3
C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
为了将两个递增的有序链表合并成一个新的递增有序链表,我们可以采用迭代的方式。以下是C语言的算法描述及示例代码:
算法步骤:
1. 初始化新链表的头节点为NULL。
2. 创建两个指针,分别指向两个输入链表的头部。
3. 比较两个链表当前节点的值,将较小的节点添加到新链表,并移动该节点到下一个位置。
4. 重复上述过程,直到其中一个链表遍历完。
5. 将另一个未遍历完的链表剩余部分添加到新链表。
C语言实现(假设`ListNode`结构包含整数`data`和指向下一个节点的指针`next`):
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int data;
struct ListNode* next;
} ListNode;
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 新链表的头节点
ListNode* head = NULL;
ListNode* current = head;
while (l1 != NULL && l2 != NULL) {
if (l1->data <= l2->data) {
current->next = l1;
l1 = l1->next;
} else {
current->next = l2;
l2 = l2->next;
}
current = current->next;
}
// 如果还有剩下的节点,直接连接到新链表
if (l1 != NULL) {
current->next = l1;
} else if (l2 != NULL) {
current->next = l2;
}
return head;
}
// 测试函数
void printList(ListNode* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
int main() {
// 例子:l1 = [1, 2, 4], l2 = [1, 3, 4]
ListNode* l1 = (ListNode*)malloc(sizeof(ListNode));
l1->data = 1;
l1->next = (ListNode*)malloc(sizeof(ListNode));
l1->next->data = 2;
l1->next->next = (ListNode*)malloc(sizeof(ListNode));
l1->next->next->data = 4;
l1->next->next->next = NULL;
ListNode* l2 = (ListNode*)malloc(sizeof(ListNode));
l2->data = 1;
l2->next = (ListNode*)malloc(sizeof(ListNode));
l2->next->data = 3;
l2->next->next = (ListNode*)malloc(sizeof(ListNode));
l2->next->next->data = 4;
l2->next->next->next = NULL;
ListNode* result = mergeTwoLists(l1, l2);
printList(result);
return 0;
}
```
当你运行这个程序时,会得到合并后的有序链表[1, 1, 2, 3, 4, 4]。注意,这个解决方案保持了原有的存储空间,没有额外分配内存。
阅读全文