用C语言将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。
时间: 2024-06-15 16:07:48 浏览: 92
要将两个递增的有序链表合并为一个递增的有序链表,可以使用双指针法来实现。具体步骤如下:
1. 定义两个指针,分别指向两个链表的头节点,假设为p1和p2。
2. 创建一个新的链表,用于存储合并后的结果,假设为mergedList。
3. 比较p1和p2指向节点的值,将较小的节点添加到mergedList中,并将对应链表的指针后移一位。
4. 重复步骤3,直到其中一个链表遍历完毕。
5. 将未遍历完的链表剩余部分直接添加到mergedList的末尾。
6. 返回mergedList作为合并后的有序链表。
下面是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*)malloc(sizeof(struct ListNode));
dummy->next = NULL;
struct ListNode* tail = dummy;
// 双指针法合并链表
while (l1 && l2) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
// 将未遍历完的链表剩余部分直接添加到结果链表的末尾
tail->next = l1 ? l1 : l2;
// 释放虚拟头节点
struct ListNode* result = dummy->next;
free(dummy);
return result;
}
// 创建链表节点
struct ListNode* createNode(int val) {
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 打印链表
void printList(struct ListNode* head) {
struct ListNode* p = head;
while (p) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");
}
int main() {
// 创建两个有序链表
struct ListNode* l1 = createNode(1);
l1->next = createNode(3);
l1->next->next = createNode(5);
struct ListNode* l2 = createNode(2);
l2->next = createNode(4);
l2->next->next = createNode(6);
// 合并两个有序链表
struct ListNode* mergedList = mergeTwoLists(l1, l2);
// 打印合并后的链表
printList(mergedList);
// 释放链表内存
struct ListNode* p = mergedList;
while (p) {
struct ListNode* temp = p;
p = p->next;
free(temp);
}
return 0;
}
```
阅读全文