将两个无序的链表合并在一起,并去除其中的重复元素,希望时间复杂度尽可能小,应该使用什么算法?请给出C语言示例
时间: 2024-05-11 21:14:36 浏览: 96
可以使用哈希表来实现。具体做法是,遍历两个链表,将每个元素的值作为键值存入哈希表中,如果发现重复元素,则将其从链表中删除。最后将两个链表合并即可。
以下是C语言示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 10000
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
int hash(int val) {
return abs(val) % HASH_SIZE;
}
ListNode* mergeLists(ListNode* l1, ListNode* l2) {
ListNode* head = NULL;
ListNode* tail = NULL;
ListNode* p = l1 ? l1 : l2;
ListNode* q = l1 && l2 ? l2 : NULL;
int h[HASH_SIZE] = {0};
while (p) {
int key = hash(p->val);
if (h[key] == 0) {
h[key] = 1;
if (!head) {
head = tail = p;
} else {
tail->next = p;
tail = p;
}
}
p = p->next;
}
while (q) {
int key = hash(q->val);
if (h[key] == 0) {
h[key] = 1;
if (!head) {
head = tail = q;
} else {
tail->next = q;
tail = q;
}
}
q = q->next;
}
if (tail) {
tail->next = NULL;
}
return head;
}
void printList(ListNode* head) {
ListNode* p = head;
while (p) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");
}
int main() {
ListNode* l1 = malloc(sizeof(ListNode));
l1->val = 1;
l1->next = malloc(sizeof(ListNode));
l1->next->val = 2;
l1->next->next = malloc(sizeof(ListNode));
l1->next->next->val = 3;
l1->next->next->next = NULL;
ListNode* l2 = malloc(sizeof(ListNode));
l2->val = 2;
l2->next = malloc(sizeof(ListNode));
l2->next->val = 3;
l2->next->next = malloc(sizeof(ListNode));
l2->next->next->val = 4;
l2->next->next->next = NULL;
ListNode* head = mergeLists(l1, l2);
printList(head);
return 0;
}
```
阅读全文