实现删除单链表中值相同的多余结点的算法
时间: 2023-04-15 17:04:04 浏览: 248
删除单链表中值相同的多余结点的算法
可以使用双重循环遍历单链表,对于每个结点,再遍历其后续结点,如果有值相同的结点,则将其删除。具体实现如下:
1. 定义两个指针p和q,初始时p指向链表的头结点,q指向p的下一个结点。
2. 循环遍历链表,对于每个结点p,再循环遍历其后续结点,对于每个结点q,如果q的值与p相同,则将q从链表中删除。
3. 删除结点q的方法为:将p的next指针指向q的下一个结点,然后释放q的内存空间。
4. 如果q的值与p不同,则将q指针向后移动一位,继续循环遍历。
5. 当q指针移动到链表的末尾时,将p指针向后移动一位,继续循环遍历。
6. 当p指针移动到链表的末尾时,算法结束。
完整代码如下:
void removeDuplicates(ListNode* head) {
ListNode* p = head;
while (p != nullptr) {
ListNode* q = p->next;
while (q != nullptr) {
if (q->val == p->val) {
p->next = q->next;
delete q;
q = p->next;
} else {
q = q->next;
}
}
p = p->next;
}
}
阅读全文