AcWing 29. 删除链表中重复的节点
原题链接
中等
作者:
andream7
,
2020-12-23 09:56:56
,
所有人可见
,
阅读 248
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* head) {
// 设置一个虚拟头节点,避免特判头节点被删除的情况
auto h1 = new ListNode(-1);
h1 -> next = head;
// 头指针指向重复区间的前一个节点
auto p = h1;
// 循环的条件是 p->next 不为空
while (p->next) {
// 尾指针指向重复区间的后一个节点
auto q = p->next;
while (q && p->next->val == q->val) q = q->next;
// 头指针和尾指针之间没有重复元素
if (p->next->next == q)
// 头指针移动到下一个节点
p = p->next;
else p->next = q; // 如果有重复元素,直接删除
}
return h1->next;
}
};