将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。用C语言代码实现
时间: 2024-10-07 10:08:03 浏览: 24
将两个递增的有序链表合并成一个递增的有序链表,可以采用迭代的方式,从头节点开始比较两个链表的当前节点值,选择较小的一个作为新链表的节点,并将其指针向后移动,直到其中一个链表遍历完。这里是一个简单的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 初始化新的链表头节点和临时指针
ListNode* head = NULL;
ListNode* tail = NULL;
// 当任一链表未遍历完
while (l1 != NULL && l2 != NULL) {
if (l1->val <= l2->val) {
// 如果l1的值小,添加到新链表
if (head == NULL) {
head = l1;
tail = l1;
} else {
tail->next = l1;
tail = l1;
}
l1 = l1->next;
} else {
// 否则,如果l2的值小,添加到新链表
if (head == NULL) {
head = l2;
tail = l2;
} else {
tail->next = l2;
tail = l2;
}
l2 = l2->next;
}
}
// 如果其中一个链表已遍历完,将另一个剩余部分添加到新链表
if (l1 != NULL) {
tail->next = l1;
} else {
tail->next = l2;
}
return head;
}
// 测试函数
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->val);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
// 创建示例链表
ListNode* l1 = (ListNode*)malloc(sizeof(ListNode));
l1->val = 1;
l1->next = (ListNode*)malloc(sizeof(ListNode));
l1->next->val = 2;
l1->next->next = NULL;
ListNode* l2 = (ListNode*)malloc(sizeof(ListNode));
l2->val = 3;
l2->next = (ListNode*)malloc(sizeof(ListNode));
l2->next->val = 4;
l2->next->next = NULL;
// 合并链表
ListNode* mergedList = mergeTwoLists(l1, l2);
// 打印合并后的链表
printList(mergedList);
return 0;
}
```
运行这个程序,你会看到合并后的有序链表是 `1 -> 2 -> 3 -> 4 -> NULL`。
阅读全文