用c语言写完整个程序代码,将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。
时间: 2024-09-22 16:06:32 浏览: 39
pta题库答案c语言之线性结构1两个有序链表序列的合并.zip
在C语言中,你可以使用迭代的方式来合并两个递增有序链表。这里是一个完整的示例程序:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct ListNode {
int val; // 节点值
struct ListNode* next; // 指向下一个节点的指针
} ListNode;
// 创建新节点函数
ListNode* createNode(int val) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
return NULL;
}
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 合并两个有序链表函数
ListNode* mergeSortedLists(ListNode* list1, ListNode* list2) {
ListNode* dummyHead = createNode(0); // 创建虚拟头节点
ListNode* tail = dummyHead; // 尾部指针
while (list1 != NULL && list2 != NULL) {
if (list1->val <= list2->val) {
tail->next = list1;
list1 = list1->next;
} else {
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
// 如果其中一个链表还有剩余元素
if (list1 != NULL) {
tail->next = list1; // 添加剩下的第一个链表元素
} else {
tail->next = list2; // 添加剩下的第二个链表元素
}
return dummyHead->next; // 返回实际的头节点
}
// 打印链表函数
void printList(ListNode* head) {
ListNode* current = head;
while (current != NULL) {
printf("%d -> ", current->val);
current = current->next;
}
printf("NULL\n");
}
int main() {
// 测试例子,假设输入是已经排序好的链表
ListNode* list1 = createNode(1);
list1->next = createNode(3);
list1->next->next = createNode(5);
ListNode* list2 = createNode(2);
list2->next = createNode(4);
list2->next->next = createNode(6);
ListNode* mergedList = mergeSortedLists(list1, list2);
printList(mergedList); // 输出:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
free(mergedList); // 注意释放内存
free(list1);
free(list2);
return 0;
}
```
这个程序首先创建了一个虚拟头节点`dummyHead`,然后遍历两个链表,每次比较当前节点的值,选择较小的一个添加到结果链表,并更新尾部指针。最后返回实际的头节点。
阅读全文