实现两个有序表的合并,用c语言解决
时间: 2024-10-10 08:04:54 浏览: 6
在C语言中,实现两个有序表的合并通常会采用递归或迭代的方式。这里我们提供一种常见的递归算法来合并两个升序排列的链表。假设我们有链表结构如下:
```c
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
```
合并两个有序链表的函数可以这样实现:
```c
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 如果其中一个链表为空,则直接返回另一个链表
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
// 比较当前两个节点的值,将较小的那个节点添加到结果链表,并移动指向下一个节点
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
```
这个函数通过不断比较并链接较小的节点,直到其中一个链表遍历完,然后将剩余的链表连接到已合并部分。
相关问题
两个有序链表的合并c语言
两个有序链表的合并可以使用递归或迭代的方式实现。以下是迭代的实现方式:
```c
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
struct ListNode dummy;
struct ListNode *tail = &dummy;
dummy.next = NULL;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
if (l1) {
tail->next = l1;
} else {
tail->next = l2;
}
return dummy.next;
}
```
这个函数接受两个有序链表 `l1` 和 `l2`,返回一个新的有序链表,包含了 `l1` 和 `l2` 中所有节点。我们使用一个虚拟头节点 `dummy` 和一个尾指针 `tail` 来构建新的链表。在循环中,我们比较 `l1` 和 `l2` 的头节点,将较小的节点接到新链表的尾部,并将对应的链表头指针向后移动。最后,如果其中一个链表还有剩余节点,我们将其全部接到新链表的尾部。
7-51 两个有序链表序列的合并使用C语言实现
以下是使用C语言实现合并两个有序链表序列的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
typedef struct Node {
int value; // 值
struct Node *next; // 指向下一个节点的指针
} Node;
// 合并两个有序链表
Node *mergeLists(Node *list1, Node *list2) {
Node *head = NULL; // 合并后链表的头节点
Node *tail = NULL; // 合并后链表的尾节点
// 如果有一个链表为空,则直接返回另一个链表
if (list1 == NULL) {
return list2;
} else if (list2 == NULL) {
return list1;
}
// 选择头节点
if (list1->value < list2->value) {
head = list1;
list1 = list1->next;
} else {
head = list2;
list2 = list2->next;
}
tail = head;
// 循环合并两个链表
while (list1 != NULL && list2 != NULL) {
if (list1->value < list2->value) {
tail->next = list1;
list1 = list1->next;
} else {
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
// 将剩余的节点添加到尾部
if (list1 != NULL) {
tail->next = list1;
} else {
tail->next = list2;
}
return head;
}
// 打印链表
void printList(Node *list) {
while (list != NULL) {
printf("%d ", list->value);
list = list->next;
}
printf("\n");
}
int main() {
// 创建两个有序链表
Node *list1 = (Node *) malloc(sizeof(Node));
list1->value = 1;
list1->next = (Node *) malloc(sizeof(Node));
list1->next->value = 3;
list1->next->next = (Node *) malloc(sizeof(Node));
list1->next->next->value = 5;
list1->next->next->next = NULL;
Node *list2 = (Node *) malloc(sizeof(Node));
list2->value = 2;
list2->next = (Node *) malloc(sizeof(Node));
list2->next->value = 4;
list2->next->next = (Node *) malloc(sizeof(Node));
list2->next->next->value = 6;
list2->next->next->next = NULL;
// 合并两个有序链表
Node *mergedList = mergeLists(list1, list2);
// 打印合并后的链表
printList(mergedList);
return 0;
}
```
输出结果为:
```
1 2 3 4 5 6
```