c++实现有序链表的合并
时间: 2023-09-12 20:02:35 浏览: 58
假设有两个有序链表A和B,现在要将它们合并成一个有序链表C。可以按照以下步骤实现:
1. 定义一个新的链表C,并初始化为空。
2. 定义三个指针pA、pB、pC,分别指向链表A、B、C的头节点。
3. 比较pA和pB所指向节点的值,将较小的节点插入到链表C的尾部,并将pC指向新插入的节点。
4. 移动指针pA或pB到下一个节点,再重复步骤3,直到其中一个链表遍历完毕。
5. 将另一个链表剩余的节点插入到链表C的尾部。
以下是具体的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 *pA = l1, *pB = l2, *pC = NULL, *tail = NULL;
struct ListNode *head = (struct ListNode*) malloc(sizeof(struct ListNode));
head->next = NULL;
pC = tail = head;
while (pA && pB) {
if (pA->val <= pB->val) {
tail->next = pA;
tail = pA;
pA = pA->next;
} else {
tail->next = pB;
tail = pB;
pB = pB->next;
}
}
if (pA) {
tail->next = pA;
} else {
tail->next = pB;
}
pC = head->next;
free(head);
return pC;
}
```
该函数的时间复杂度为O(m+n),其中m和n分别为两个链表的长度。