任务3:有序单链表的合并 有两个有序单链表LA和LB,其元素均为非递减的有序排列,请编写算法实现将这两个有序单链表合并为一个新的有序单链表。 要求:新表不能额外申请结点空间,要有效利用现有两个单链表的结点空间。 程序代码:
时间: 2024-09-27 17:08:56 浏览: 11
对于这个问题,我们可以使用迭代的方式来合并两个有序的单链表,而不需要额外的空间。以下是C语言的一个示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int data;
struct ListNode* next;
} ListNode;
// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* la, ListNode* lb) {
// 初始化结果链表
ListNode* result = NULL;
// 当其中一个链表为空时,直接返回另一个链表
if (la == NULL) {
return lb;
} else if (lb == NULL) {
return la;
}
// 比较两个链表当前节点的数据大小
if (la->data <= lb->data) {
// 结果链表接上LA的节点,并更新指针
result = la;
la = la->next;
} else {
// 结果链表接上LB的节点,并更新指针
result = lb;
lb = lb->next;
}
// 递归地继续比较并合并两个链表的剩余部分
return result == NULL ? lb : mergeTwoLists(la, lb);
}
// 打印链表
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
// 创建两个例子的有序链表
// ...
// 实现LA和LB的初始化...
// 调用合并函数
ListNode* mergedHead = mergeTwoLists(LA, LB);
printf("Merged list: \n");
printList(mergedHead);
return 0;
}
```
这段代码定义了一个`mergeTwoLists`函数,它通过比较两个链表当前节点的值,选择较小的那个添加到结果链表中,并递归地处理剩余的链表。当其中一个链表变为NULL时,就返回另一个链表作为结果。在`main`函数里,你需要自己提供两个有序链表`LA`和`LB`的初始化。