两个指针删除单链表中重复元素c
时间: 2024-02-25 14:58:14 浏览: 17
可以使用两个指针,一个指针p遍历单链表,另一个指针q指向当前已经处理好的、不包含重复元素的链表的最后一个节点。如果p所指向的节点的值在链表中不重复,就将其接到q节点后面,并将q指向该节点。如果p所指向的节点的值在链表中重复,就将其删除。
具体实现代码如下:
```c
void deleteDuplicates(ListNode* head) {
if (head == NULL) return;
ListNode* p = head; // p指针遍历单链表
ListNode* q = head; // q指针指向当前已经处理好的、不包含重复元素的链表的最后一个节点
while (p != NULL) {
bool isDuplicate = false; // 标记p指针指向的节点是否重复
ListNode* r = p->next; // r指针用于查找p指针指向的节点是否重复
while (r != NULL) {
if (p->val == r->val) {
isDuplicate = true; // 如果p指针指向的节点重复,标记isDuplicate为true
break;
}
r = r->next;
}
if (!isDuplicate) { // 如果p指针指向的节点不重复,将其接到q节点后面,并将q指向该节点
q->next = p;
q = p;
}
p = p->next;
}
q->next = NULL; // 将q节点的next指针置为NULL,表示链表的结尾
}
```
需要注意的是,在删除重复元素时,需要将重复元素的节点从链表中删除,并释放其内存空间。这里的代码没有给出释放内存空间的部分,需要根据实际情况进行处理。