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