将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍然使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复数据。
时间: 2024-10-08 11:06:00 浏览: 32
要将两个递增的有序链表合并成一个新的递增有序链表,可以采用迭代或递归的方式。这里我提供一种基于迭代的方法,它不需要额外的空间,并确保没有重复的数据。
首先,我们需要定义链表节点结构:
```c
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
```
然后,我们可以创建一个辅助函数 `mergeTwoLists` 来执行合并操作:
```c
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 初始化空链表头节点
ListNode dummy(0, NULL);
// 定义三个指针:指向当前合并点、l1 和 l2 的头部
ListNode *cur = &dummy;
ListNode *l1_ptr = l1;
ListNode *l2_ptr = l2;
while (l1_ptr != NULL && l2_ptr != NULL) {
if (l1_ptr->val < l2_ptr->val) {
cur->next = l1_ptr;
l1_ptr = l1_ptr->next;
} else if (l1_ptr->val > l2_ptr->val) {
cur->next = l2_ptr;
l2_ptr = l2_ptr->next;
} else { // 如果值相等,只添加一次(去重)
if (l1_ptr == l2_ptr) { // 避免重复添加同一个节点
l1_ptr = l1_ptr->next;
l2_ptr = l2_ptr->next;
} else {
cur->next = l1_ptr; // 将第一个节点加入
l1_ptr = l1_ptr->next;
}
}
cur = cur->next;
}
// 添加剩余未遍历完的链表节点
if (l1_ptr != NULL) {
cur->next = l1_ptr;
} else {
cur->next = l2_ptr;
}
return dummy.next; // 返回新的链表头
}
```
在这个函数中,我们使用了两个指针 `l1_ptr` 和 `l2_ptr` 分别跟踪两个链表中的元素,然后根据元素大小决定将哪个元素插入到新链表中。如果发现值相等,则仅添加其中一个节点以避免重复。当遍历完其中一个链表时,只需将剩余的链表连接到新链表的末尾。
阅读全文