C语言实现,将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
时间: 2024-10-29 17:16:29 浏览: 34
设计算法合并非递减有序链表
5星 · 资源好评率100%
在C语言中,合并两个非递减的有序链表为一个非递增的有序链表可以采用双指针法来实现,同时考虑到链表的特性,我们可以使用原地合并的方式来避免额外的空间开销。以下是步骤:
1. 创建一个新的头节点 `merged` 和两个指针 `p1` 和 `p2` 分别指向两个输入链表的头部。
2. 比较 `p1` 和 `p2` 所指的节点值,选择较小的一个将当前节点赋给 `merged`,然后移动该节点的指针(即 `p1` 或 `p2`),指向下一个较小的节点。如果其中一个链表结束,就直接连接另一个链表剩余部分到 `merged` 的尾部。
3. 当 `p1` 和 `p2` 都到达链表末尾时,说明遍历完成,`merged` 就是我们想要的结果。
下面是一个简单的伪代码实现:
```c
struct Node {
int val;
struct Node *next;
};
// 函数原型
struct Node* mergeTwoLists(struct Node* l1, struct Node* l2);
// 合并函数
struct Node* mergeTwoLists(struct Node* l1, struct Node* l2) {
// 创建临时头结点
struct Node *merged = (l1 ? l1 : l2);
struct Node *p1 = l1, *p2 = l2;
while (p1 && p2) {
if (p1->val <= p2->val) {
merged->next = p1;
p1 = p1->next;
} else {
merged->next = p2;
p2 = p2->next;
}
merged = merged->next;
}
// 如果还有剩余节点,连接到新链表尾部
if (p1)
merged->next = p1;
else if (p2)
merged->next = p2;
return merged;
}
```
阅读全文