已知链表结构为:typedef struct Node{int data; struct Node *next;}Node;编写函数实现:合并两个有序链表(从小到大),使之仍然有序(依然从小到大)。函数原型为:Node * merge(Node*h1,Node*h2);(不需要写main函数)
时间: 2023-11-30 22:02:40 浏览: 92
好的,根据您提供的需求,以下是实现合并两个有序链表的函数:
```c
Node * merge(Node* h1, Node* h2) {
if(h1 == NULL) return h2; // 如果h1为空,直接返回h2
if(h2 == NULL) return h1; // 如果h2为空,直接返回h1
Node* head = NULL; // 合并后链表的头结点
Node* tail = NULL; // 合并后链表的尾结点
// 选取头结点
if(h1->data < h2->data) {
head = h1;
h1 = h1->next;
} else {
head = h2;
h2 = h2->next;
}
tail = head; // 初始化尾结点为头结点
// 比较两个链表中的结点,将较小的结点插入到合并后的链表中
while(h1 != NULL && h2 != NULL) {
if(h1->data < h2->data) {
tail->next = h1;
h1 = h1->next;
} else {
tail->next = h2;
h2 = h2->next;
}
tail = tail->next; // 更新尾结点
}
// 将剩余的结点插入到合并后的链表中
if(h1 != NULL) {
tail->next = h1;
} else {
tail->next = h2;
}
return head;
}
```
这个函数的主要思路是:分别遍历两个有序链表,比较每个结点的大小,将较小的结点插入到合并后的链表中,最终返回合并后的链表的头结点。
阅读全文