链表怎么去除重复元素
时间: 2024-01-04 10:16:20 浏览: 31
可以使用哈希表来实现链表去重。具体做法是遍历链表,将每个节点的值存入哈希表中,如果发现重复的节点,则将该节点从链表中删除即可。
代码示例:
```
def remove_duplicates(head):
if not head:
return head
seen = set()
seen.add(head.val)
curr = head
while curr.next:
if curr.next.val in seen:
curr.next = curr.next.next
else:
seen.add(curr.next.val)
curr = curr.next
return head
```
相关问题
删除链表中重复元素 c语言
在C语言中删除链表中重复元素,可以采用双重循环的方式,对链表进行遍历,每当遇到重复的元素,就将其删除即可。具体实现步骤如下:
1. 定义一个指针p1,指向链表的第一个节点。
2. 对链表进行遍历,遍历过程中使用指针p2指向当前节点的下一个节点。
3. 在p2指向的节点后面进行另一次循环,如果发现p2指向的节点与当前节点p1指向的节点相同,则将p2所指向的节点删除。
4. 将p2指向下一个节点,继续进行循环操作,直到p2指向链表末尾。
5. 将p1指向下一个节点,重复以上操作,直到遍历到链表末尾。
以下是一段示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} Node;
Node* deleteDuplicates(Node* head) {
if (head == NULL) {
return NULL;
}
Node *p1 = head;
while (p1 != NULL) {
Node *p2 = p1;
while (p2->next != NULL) {
if (p1->data == p2->next->data) {
Node *tmp = p2->next;
p2->next = tmp->next;
free(tmp);
} else {
p2 = p2->next;
}
}
p1 = p1->next;
}
return head;
}
int main() {
// 创建链表
Node *head = (Node*)malloc(sizeof(Node));
head->data = 1;
head->next = NULL;
Node *p = head;
for (int i = 2; i <= 5; i++) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = i % 3 + 1;
newNode->next = NULL;
p->next = newNode;
p = newNode;
}
// 删除重复元素
head = deleteDuplicates(head);
// 输出链表
p = head;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
// 释放内存
p = head;
while (p != NULL) {
Node *tmp = p;
p = p->next;
free(tmp);
}
return 0;
}
删除链表的重复元素ii
好的,让我来帮您解决这个问题。删除链表的重复元素ii可以采用两个指针的方法,一个指针p指向当前节点,另一个指针q用来查找重复值。具体实现可以参考以下代码:
```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode dummy(-1);
dummy.next = head;
ListNode *p = &dummy;
ListNode *q = head;
while (q) {
while (q->next && q->val == q->next->val) {
q = q->next;
}
if (p->next == q) {
p = p->next;
} else {
p->next = q->next;
}
q = q->next;
}
return dummy.next;
}
};
```
这段代码会对链表进行遍历,找出重复的元素并删除。希望能够帮到您,有问题可以继续提问哦。