用C语言写一个程序,将两个递增的有序链表合并成一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间,表中不允许有重复数据
时间: 2024-11-21 22:23:19 浏览: 9
约瑟夫环 (Yosephus Problem) c 语言实现
在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) {
newNode->data = data;
newNode->next = NULL;
}
return newNode;
}
// 合并两个递增有序链表
Node* mergeSortedLists(Node* headA, Node* headB) {
Node* mergedHead = NULL; // 结果链表头指针
Node* current = NULL; // 当前遍历节点
// 判断两个链表哪一个是空的或较小
if (headA == NULL) {
return headB;
} else if (headB == NULL) {
return headA;
} else if (headA->data <= headB->data) {
mergedHead = headA;
current = headA;
} else {
mergedHead = headB;
current = headB;
}
while (headA != NULL && headB != NULL) {
// 如果第一个链表当前元素小于第二个,添加到结果链表
if (current->data < headA->data && current->data < headB->data) {
if (mergedHead == current) { // 首次添加,更新头指针
mergedHead = mergedHead->next;
}
current->next = createNode(current->data);
current = current->next;
} else {
// 添加剩余列表中的较小元素
if (headA->data <= headB->data) {
current->next = headA;
headA = headA->next;
} else {
current->next = headB;
headB = headB->next;
}
current = current->next;
}
}
// 将剩余的链表添加到结果链表
if (headA != NULL) {
current->next = headA;
} else {
current->next = headB;
}
return mergedHead;
}
int main() {
// 示例链表创建
Node* listA = createNode(1); // [1]
listA->next = createNode(3); // [1, 3]
listA->next->next = createNode(5); // [1, 3, 5]
Node* listB = createNode(2); // [2]
listB->next = createNode(4); // [2, 4]
listB->next->next = createNode(6); // [2, 4, 6]
Node* result = mergeSortedLists(listA, listB);
// 打印结果链表
Node* temp = result;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
return 0;
}
```
运行上述程序会得到合并后的有序链表:[1, 2, 3, 4, 5, 6]。
阅读全文