假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表。
时间: 2023-04-26 21:02:21 浏览: 170
已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)
算法步骤如下:
1. 定义三个指针p、q、r,分别指向两个单链表的头结点和归并后的单链表的头结点。
2. 比较p和q指向的结点的元素值大小,将较小的结点插入到归并后的单链表的头部,并将指针后移。
3. 重复步骤2,直到p或q指向的链表为空。
4. 将p或q指向的链表剩余的结点插入到归并后的单链表的头部。
5. 返回归并后的单链表的头结点。
具体实现代码如下:
```
typedef struct Node {
int data;
struct Node *next;
} Node, *LinkedList;
LinkedList mergeLinkedList(LinkedList list1, LinkedList list2) {
Node *p = list1->next;
Node *q = list2->next;
Node *r = NULL;
list1->next = NULL;
while (p && q) {
if (p->data < q->data) {
Node *temp = p->next;
p->next = r;
r = p;
p = temp;
} else {
Node *temp = q->next;
q->next = r;
r = q;
q = temp;
}
}
while (p) {
Node *temp = p->next;
p->next = r;
r = p;
p = temp;
}
while (q) {
Node *temp = q->next;
q->next = r;
r = q;
q = temp;
}
list2->next = NULL;
list1->next = r;
return list1;
}
```
阅读全文