设ha和hb分别是两个带头结点的递增有序单链表。C语言设计一个算法,将这两个有序链表的所有数据结点合并成一个递增有序的单链表hc,并用相关数据进行测试。
时间: 2024-09-26 15:02:11 浏览: 7
在 C 语言中,我们可以设计一个合并两个有序链表的算法,通常采用迭代或递归的方式实现。这里我将提供一个迭代方法的伪代码描述:
```c
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* mergeSortedLists(Node* ha, Node* hb) {
// 创建一个新的头节点
Node* hc = (ha == NULL) ? hb : (hb == NULL) ? ha : (ha->data < hb->data ? ha : hb);
// 当其中一个列表为空时,直接将另一个列表添加到结果链表
while (ha && hb) {
if (ha->data < hb->data) {
hc->next = ha;
ha = ha->next;
} else {
hc->next = hb;
hb = hb->next;
}
hc = hc->next;
}
// 如果还有剩余的节点,则将其添加到结果链表
if (ha) {
hc->next = ha;
} else if (hb) {
hc->next = hb;
}
return hc;
}
// 测试示例
void testMerge() {
// 初始化两个递增有序链表
Node* listA = createLinkedList({1, 3, 5});
Node* listB = createLinkedList({2, 4, 6});
Node* result = mergeSortedLists(listA, listB);
// 打印合并后的链表
printLinkedList(result);
}
// 辅助函数:创建链表,插入数据
Node* createLinkedList(int arr[]) {
//...
}
// 辅助函数:打印链表
void printLinkedList(Node* head) {
//...
}
```
在这个算法中,我们首先比较两个链表当前节点的数据值,选择较小的一个添加到新链表`hc`,然后移动指向下一个最小值的指针。最后处理剩余链表的情况。