写出两个循环链表的合并算法描述,类c语言代码表示
时间: 2024-09-29 21:04:02 浏览: 42
合并两个循环链表可以使用迭代或递归的方式来实现。这里提供一个简单的迭代方法的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) {
printf("Memory allocation failed.\n");
return NULL;
}
newNode->data = data;
newNode->next = newNode; // 循环链表特性
return newNode;
}
// 合并两个循环链表
Node* mergeTwoLists(Node* list1, Node* list2) {
Node* dummyHead = (Node*)malloc(sizeof(Node)); // 创建虚拟头节点
dummyHead->next = list1;
Node* current = dummyHead;
while (list1 != NULL && list2 != NULL) { // 只要两个列表非空
if (list1->data <= list2->data) { // 比较当前节点值
current->next = list1;
list1 = list1->next;
} else {
current->next = list2;
list2 = list2->next;
}
current = current->next; // 移动到下一个比较点
}
// 如果其中一个链表还有剩余元素
if (list1 != NULL) {
current->next = list1;
} else {
current->next = list2;
}
return dummyHead->next; // 返回新合并后的第一个节点
}
void printList(Node* head) {
while (head != head->next) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main() {
// 创建两个循环链表作为例子,这里省略链表创建过程
Node* list1 = ...;
Node* list2 = ...;
Node* mergedList = mergeTwoLists(list1, list2);
printf("Merged list: ");
printList(mergedList);
free(mergedList); // 释放内存
return 0;
}
阅读全文