递增有序单链表L1、L2,不申请新结点,利用原表结点对两表进行合并,并使得合并后成为一个集合,合并后用L1的头结点作为头结点,删除多余的结点,删除L2的头结点。
时间: 2023-05-31 18:01:32 浏览: 18
算法步骤如下:
1. 定义指针p1、p2分别指向L1的头结点和L2的头结点。
2. 若L1为空,则直接让L1指向L2,返回L1。
3. 若L2为空,则直接返回L1。
4. 若L1和L2均不为空,则从头开始比较L1和L2的结点大小,将小的结点接到新的链表中。
5. 每次比较时将p1或p2指向下一个结点,直到p1或p2为空。
6. 若p1为空,则将p2接到新的链表中。
7. 若p2为空,则新的链表已经包含了L1和L2的所有结点,不需要再做处理。
8. 最后删除L2的头结点,返回L1。
相关问题
编写将两个带头结点的递增有序单链表l1和l2合并为一个非递减的有序单链表l1的算法 merge( linklist &l1, linklist &l2 ),要求直接使用原链表中的结点。
算法思路:
1. 定义两个指针p1和p2分别指向链表l1和l2的第一个结点(即头结点的下一个结点);
2. 定义一个指针p3指向新链表l3的头结点;
3. 比较p1和p2所指向的结点的值,将较小的结点插入到新链表l3的尾部,并将指向该结点的指针后移;
4. 重复步骤3,直到p1或p2为空;
5. 将p1或p2剩余的结点插入到新链表l3的尾部;
6. 返回新链表l3的头结点。
算法实现:
```
typedef struct node {
int data;
struct node *next;
} Node, *LinkList;
LinkList merge(LinkList &l1, LinkList &l2) {
LinkList p1 = l1->next, p2 = l2->next, p3 = l1;
while (p1 && p2) {
if (p1->data <= p2->data) {
p3->next = p1;
p1 = p1->next;
} else {
p3->next = p2;
p2 = p2->next;
}
p3 = p3->next;
}
p3->next = p1 ? p1 : p2;
return l1;
}
```
注:本算法假设链表中不含有重复元素。如果链表中含有重复元素,需要对算法进行修改。
用线性表将两个递增的线性表合并成一个非递减线性表,要求利用原表的结点空间结构构造新表
算法思路:
1.定义两个指针分别指向两个递增的线性表的头结点;
2.新建一个空的线性表作为合并后的结果;
3.比较两个指针指向结点的大小,将小的结点插入新表中;
4.将小的结点的指针向后移动一位;
5.重复执行3、4两步,直到其中一个表的指针指向空;
6.将另一个表剩余的结点插入新表中;
7.返回合并后的结果。
实现代码如下(C语言):
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int data;
struct Node *next;
}Node, *LinkedList;
LinkedList createList(int n) { // 创建一个长度为n的有序线性表
LinkedList head = (LinkedList)malloc(sizeof(Node));
head->next = NULL;
LinkedList p = head;
int i;
for (i = 0; i < n; i++) {
LinkedList newNode = (LinkedList)malloc(sizeof(Node));
scanf("%d", &newNode->data);
newNode->next = NULL;
p->next = newNode;
p = p->next;
}
return head;
}
LinkedList mergeList(LinkedList l1, LinkedList l2) { // 合并两个有序线性表
LinkedList head = (LinkedList)malloc(sizeof(Node));
head->next = NULL;
LinkedList p = head;
LinkedList p1 = l1->next;
LinkedList p2 = l2->next;
while (p1 != NULL && p2 != NULL) {
if (p1->data <= p2->data) {
p->next = p1;
p1 = p1->next;
} else {
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if (p1 == NULL) {
p->next = p2;
} else {
p->next = p1;
}
return head;
}
void printList(LinkedList list) { // 输出链表中的元素
LinkedList p = list->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
int n, m;
printf("请输入有序线性表1的长度:");
scanf("%d", &n);
printf("请输入有序线性表1的元素:");
LinkedList l1 = createList(n);
printf("请输入有序线性表2的长度:");
scanf("%d", &m);
printf("请输入有序线性表2的元素:");
LinkedList l2 = createList(m);
printf("合并后的非递减线性表为:");
LinkedList l3 = mergeList(l1, l2);
printList(l3);
return 0;
}
```
运行结果:
```
请输入有序线性表1的长度:3
请输入有序线性表1的元素:1 3 5
请输入有序线性表2的长度:4
请输入有序线性表2的元素:2 4 6 8
合并后的非递减线性表为:1 2 3 4 5 6 8
```