请用 C 语言编写算法将两个给定的有序单链表(带头结点)合并成一个有序单链表,要求使用两个有序单链表的原有空间进行合并。 typedef int elemtype ; typedef struct Node{ elemtype data ; struct Node * next ; } Inode , linklist ;//单链表定义 int empty ( linklist * A );//判断链表是否为空,返回值为0则链表为空 int length ( linklist * A );//返回单链表 A 的长度 请使用以上定义和基本操作完成如下函数定义。 linklist * merge(linklist * A,linklist * B);//假设单链表A、B已经有序,返回合并后的单链表头指针
时间: 2024-03-17 21:41:19 浏览: 18
下面是使用 C 语言编写的算法,将两个有序单链表合并成一个有序单链表:
```c
linklist * merge(linklist * A, linklist * B)
{
Inode *p = A->next, *q = B->next, *s = A;
while (p != NULL && q != NULL) {
if (p->data <= q->data) {
s->next = p;
s = p;
p = p->next;
} else {
s->next = q;
s = q;
q = q->next;
}
}
if (p != NULL) {
s->next = p;
}
if (q != NULL) {
s->next = q;
}
free(B);
return A;
}
```
该函数的主要思路是使用两个指针 `p` 和 `q` 分别指向链表 A 和 B 的第一个结点,然后比较它们的值,将较小的值插入到新的链表中,直到其中一个链表为空。最后将另一个链表剩余的结点直接插入到新的链表的末尾即可。最后释放链表 B 的头结点,返回链表 A 的头指针。