将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。用C实现,给出程序的完成代码
时间: 2024-03-14 15:43:22 浏览: 34
好的,这是一个经典的链表问题,可以使用双指针法来合并两个有序链表。以下是C语言实现的代码:
```c
#include <stdio.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *p1 = l1, *p2 = l2, *p3 = NULL, *head = NULL;
if (!l1) return l2;
if (!l2) return l1;
if (l1->val < l2->val) {
head = l1;
p3 = l1;
p1 = p1->next;
} else {
head = l2;
p3 = l2;
p2 = p2->next;
}
while (p1 && p2) {
if (p1->val < p2->val) {
p3->next = p1;
p1 = p1->next;
} else {
p3->next = p2;
p2 = p2->next;
}
p3 = p3->next;
}
if (p1) {
p3->next = p1;
} else if (p2) {
p3->next = p2;
}
return head;
}
int main() {
ListNode n1 = {1, NULL};
ListNode n2 = {2, NULL};
ListNode n3 = {4, NULL};
n1.next = &n2;
n2.next = &n3;
ListNode n4 = {1, NULL};
ListNode n5 = {3, NULL};
ListNode n6 = {4, NULL};
n4.next = &n5;
n5.next = &n6;
ListNode *result = mergeTwoLists(&n1, &n4);
while (result) {
printf("%d ", result->val);
result = result->next;
}
printf("\n");
return 0;
}
```
在这个实现中,我们使用三个指针 `p1`、`p2` 和 `p3` 分别指向两个链表和合并后的链表。我们还使用了一个头指针 `head` 来存储合并后的链表的头节点。
首先,我们对特殊情况进行了处理,即其中一个链表为空。然后,我们比较两个链表的头节点的值,选择较小的节点作为合并后链表的头节点。然后,我们移动指针 `p1` 或 `p2`,直到其中一个链表为空。在移动指针的过程中,我们使用指针 `p3` 来表示合并后链表的尾节点,并将指针 `p3` 指向当前较小的节点。最后,如果还有剩余的节点,我们将其添加到合并后链表的尾部。
以上就是一个简单的链表合并算法的实现,希望能够帮助到您。