请编写一个完整的c语言程序:将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍然使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复数据。
时间: 2024-10-08 17:05:40 浏览: 30
当合并两个递增有序链表时,我们需要遍历每个链表,比较节点值并将较小的节点添加到新链表中。同时,我们还需要处理可能的重复节点。以下是一个简单的C语言程序示例,实现了这个功能:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 合并两个有序链表
Node* mergeSortedLists(Node* list1, Node* list2) {
// 初始化结果链表头结点为NULL
Node* mergedList = NULL;
// 指针用于遍历链表
Node* ptr1 = list1, *ptr2 = list2, *mergedPtr = mergedList;
while (ptr1 != NULL && ptr2 != NULL) {
// 比较节点值
if (ptr1->data <= ptr2->data) {
// 将较小节点添加到合并后的链表
if (mergedPtr == NULL) {
mergedList = ptr1; // 如果合并链表为空,直接设置
} else {
mergedPtr->next = ptr1;
}
ptr1 = ptr1->next;
} else {
// 否则,将较大节点添加到合并后的链表
if (mergedPtr == NULL) {
mergedList = ptr2;
} else {
mergedPtr->next = ptr2;
}
ptr2 = ptr2->next;
}
mergedPtr = mergedPtr->next; // 更新合并指针
}
// 如果其中一个链表未遍历完,将其剩余部分追加到合并链表末尾
while (ptr1 != NULL) {
if (mergedPtr == NULL) {
mergedList = ptr1;
} else {
mergedPtr->next = ptr1;
}
ptr1 = ptr1->next;
mergedPtr = mergedPtr->next;
}
while (ptr2 != NULL) {
if (mergedPtr == NULL) {
mergedList = ptr2;
} else {
mergedPtr->next = ptr2;
}
ptr2 = ptr2->next;
mergedPtr = mergedPtr->next;
}
return mergedList;
}
// 打印链表
void printList(Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main() {
// 假设你已经有了两个已排序的链表,例如:
Node* list1 = createNode(1); // 1 -> NULL
list1->next = createNode(4); // 1 -> 4 -> NULL
Node* list2 = createNode(2); // 2 -> NULL
list2->next = createNode(6); // 2 -> 6 -> NULL
Node* mergedList = mergeSortedLists(list1, list2);
// 打印合并后的链表
printList(mergedList);
return 0;
}
```
在这个例子中,`mergeSortedLists` 函数接受两个有序链表的头指针,返回一个新的有序链表,该链表包含原两个链表中的所有节点(没有重复)。`main` 函数创建了两个示例链表并调用 `mergeSortedLists` 进行合并。
如果你已经有一个实际的链表结构,并且它们是递增排序的,你可以根据链表的实际节点替换 `createNode` 函数中的节点值,然后调用 `mergeSortedLists` 方法进行合并。
阅读全文