已知L1和L2分别为两个循环单链表的头结点指针,m,n分别为L1,L2表中数据结点个数。要求设计一个算法,用最快速度将两表合并成一个带头结点的循环单链表,用C语言编写切手动输入L1,L2的数据。
时间: 2024-10-08 22:08:33 浏览: 45
数据结构试题库1
为了合并两个循环单链表 L1 和 L2,你可以使用迭代的方式,创建一个新的循环链表作为结果,并按照节点顺序链接起来。以下是 C 语言的一个简单示例,它假设用户已经分别初始化了 `L1` 和 `L2` 的头结点:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int data;
struct ListNode *next;
} ListNode;
// 创建新节点并连接到列表
ListNode* mergeLists(ListNode* head1, ListNode* head2) {
ListNode *newHead = (ListNode*)malloc(sizeof(ListNode)); // 新链表头结点
newHead->data = -1; // 使用特殊值作为初始标记,表示正在合并
ListNode *current = newHead;
while (head1 && head2) { // 当两个链表都有剩余元素
if (head1->data <= head2->data) { // 将较小的元素添加到当前链表
current->next = head1;
head1 = head1->next;
} else {
current->next = head2;
head2 = head2->next;
}
current = current->next; // 移动到下一个位置
}
// 如果有一个链表已空,则将另一个链表的所有剩余元素添加到新链表
if (head1) {
current->next = head1;
} else {
current->next = head2;
}
// 设置新的链表为循环链表
current->next->next = newHead;
return newHead;
}
// 打印链表
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
// 用户手动输入 L1 和 L2 的节点数据
// 这里仅做演示,实际应用中你需要处理输入部分
// 请替换下面的 'head1' 和 'head2' 为实际的链表头结点
ListNode* head1 = ...;
ListNode* head2 = ...;
// 合并链表
ListNode* mergedHead = mergeLists(head1, head2);
// 打印合并后的链表
printList(mergedHead);
return 0;
}
```
阅读全文