C语言已知链表结构为:typedef struct Node{int data; struct Node *next;}Node;编写函数实现:合并两个有序链表,使之仍然有序。函数原型为:Node * merge(Node*h1,Node*h2);
时间: 2023-08-07 19:05:05 浏览: 82
下面是实现合并两个有序链表的代码:
```
Node *merge(Node *h1, Node *h2) {
if (h1 == NULL) {
return h2;
}
if (h2 == NULL) {
return h1;
}
Node *head, *tail;
if (h1->data < h2->data) {
head = tail = h1;
h1 = h1->next;
} else {
head = tail = h2;
h2 = h2->next;
}
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;
}
if (h2 != NULL) {
tail->next = h2;
}
return head;
}
```
该函数接收两个有序链表的头指针 `h1` 和 `h2`,返回一个新的有序链表的头指针。该函数使用双指针法,从头开始遍历两个有序链表,比较当前节点的值大小,将小的节点插入新链表中,直到其中一个链表遍历完毕。最后将剩余的链表直接插入到新链表的末尾即可。
阅读全文