数据结构2.11将两个有序链表并为一个有序链表的主函数怎么写
时间: 2024-09-24 20:30:07 浏览: 25
合并两个有序链表的主函数通常会包含以下几个步骤:
```c++
// 定义链表节点结构体
typedef struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
} ListNode;
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 使用递归或者迭代的方式实现
if (!l1) return l2; // 如果l1为空,直接返回l2
if (!l2) return l1; // 如果l2为空,直接返回l1
// 如果l1的值小于l2,说明l1更前面,将l1的next指向下一个节点
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2); // 递归处理剩余部分
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next); // 否则,l2在前,递归处理
return l2;
}
}
```
这个`mergeTwoLists`函数接受两个头结点作为参数,通过比较它们的值并将较小的节点连接到另一个链表的剩余部分,最终返回合并后的有序链表的头节点。
相关问题
将两个有序链表并为一个有序链表
算法思路:
创建一个新的链表,用于存储合并后的有序链表。同时定义两个指针,分别指向要合并的两个有序链表的头结点。比较两个指针指向的结点的值,将较小的结点添加到新链表中,并将指向较小结点的指针后移一位。重复此过程,直到其中一个链表为空,然后将另一个链表中剩余的结点全部添加到新链表的末尾。
算法实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0) # 创建一个虚拟头结点
cur = dummy # 创建一个指针,指向新链表的末尾
while l1 and l2: # 只要两个链表都不为空,就比较它们的头结点
if l1.val <= l2.val:
cur.next = l1 # 将较小的结点添加到新链表的末尾
l1 = l1.next # 向后移动指向 l1 的指针
else:
cur.next = l2 # 将较小的结点添加到新链表的末尾
l2 = l2.next # 向后移动指向 l2 的指针
cur = cur.next # 向后移动指向新链表末尾的指针
if l1: # 如果 l1 还有剩余的结点,将它们全部添加到新链表的末尾
cur.next = l1
if l2: # 如果 l2 还有剩余的结点,将它们全部添加到新链表的末尾
cur.next = l2
return dummy.next # 返回新链表的头结点
```
时间复杂度:$O(m+n)$,其中 $m$ 和 $n$ 分别是两个有序链表的长度。
空间复杂度:$O(1)$
用c语言表示将两个有序链表合为一个有序链表
在 C 语言中,合并两个有序链表通常可以使用迭代或递归的方式实现。这里提供一个简单的迭代方法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 创建一个新的节点
ListNode* createNode(int val) {
ListNode *node = (ListNode*)malloc(sizeof(ListNode));
node->val = val;
node->next = NULL;
return node;
}
// 合并两个有序链表
ListNode* mergeTwoSortedLists(ListNode* l1, ListNode* l2) {
// 初始化空链表作为结果
ListNode* result = NULL;
// 当l1和l2都不为空时
while (l1 != NULL && l2 != NULL) {
// 如果l1的值小于l2,将其添加到结果并将l1向后移动一位
if (l1->val < l2->val) {
if (result == NULL) {
result = l1;
} else {
result->next = l1;
}
l1 = l1->next;
// 否则将l2的值添加到结果并将l2向后移动一位
} else {
if (result == NULL) {
result = l2;
} else {
result->next = l2;
}
l2 = l2->next;
}
}
// 将剩余未处理的链表连接到结果的后面
if (l1 != NULL) {
result->next = l1;
} else if (l2 != NULL) {
result->next = l2;
}
return result;
}
int main() {
// 为了演示,假设你已经创建了两个有序链表,例如:
// l1: 1 -> 3 -> 5
// l2: 2 -> 4 -> 6
// 调用mergeTwoSortedLists函数
ListNode* mergedList = mergeTwoSortedLists(l1, l2);
// 打印合并后的链表
while (mergedList != NULL) {
printf("%d ", mergedList->val);
mergedList = mergedList->next;
}
printf("\n");
return 0;
}