用类c语言设计算法将两个有序的单链表合并成一个有序的单链表,要求利用原表的结点空间。
时间: 2023-04-15 08:04:28 浏览: 251
完成多项式的相加运算
5星 · 资源好评率100%
算法步骤如下:
1. 定义一个新的链表头节点,命名为head,同时定义两个指针p和q,分别指向两个有序单链表的头节点。
2. 比较p和q指向的节点的值的大小,将较小的节点连接到head后面,同时将指向该节点的指针后移一位。
3. 重复步骤2,直到其中一个链表遍历完毕。
4. 将未遍历完的链表的剩余节点连接到head后面。
5. 返回head节点,即为合并后的有序单链表。
代码实现如下:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} Node;
Node *merge(Node *p, Node *q) {
Node *head = (Node *)malloc(sizeof(Node));
Node *r = head;
while (p && q) {
if (p->data <= q->data) {
r->next = p;
p = p->next;
} else {
r->next = q;
q = q->next;
}
r = r->next;
}
if (p) {
r->next = p;
} else {
r->next = q;
}
return head->next;
}
```
其中,p和q分别为两个有序单链表的头节点,函数返回合并后的有序单链表的头节点。
阅读全文