将两个递增的序列链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。
时间: 2024-11-21 22:14:52 浏览: 6
C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
要将两个递增的顺序链表合并成一个新的递增顺序链表,同时保持原链表的结构不变,你可以采用迭代或递归的方法。这里我会提供一种迭代的方法:
首先,我们需要定义链表节点结构(如果还没有的话):
```c
typedef struct ListNode {
int val; // 节点值
struct ListNode *next; // 指向下个节点
} ListNode;
```
然后,我们可以创建一个辅助函数`mergeLists`来完成合并:
```c
ListNode* mergeLists(ListNode* l1, ListNode* l2) {
// 创建新的头节点,用于存放合并后的链表
ListNode dummy(0, NULL); // 假设没有值的虚拟头节点
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; // 更新尾部指针
}
// 如果其中一个链表已经结束,将另一个链表剩余部分添加到新链表末尾
if (l1) {
tail->next = l1;
} else {
tail->next = l2;
}
return dummy.next; // 返回新链表的头节点
}
```
这个函数遍历两个链表,比较当前节点的值,将较小的节点添加到新链表的尾部。当一个链表遍历完后,将其剩余的部分添加到新链表的末尾。
阅读全文