AcWing 29. 删除链表中重复的节点
原题链接
中等
作者:
跟着灿哥学切菜
,
2021-02-01 14:57:23
,
所有人可见
,
阅读 267
/**
* 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) {
//凡是可能删除链表中的第一个节点的问题, 都要使用虚拟头结点的方式
ListNode * dummy = new ListNode(-1);
dummy -> next = head;
//使用两个指针来表示当前处理到哪一段,只保留长度为1的这一段, 而将长度大于1的段全部删除掉
auto p = dummy;
while (p -> next) {
auto q = p -> next; //此时q表示的是下一段的开始的位置
while (q && p -> next -> val == q -> val) q = q -> next;
//如果下一段的长度为1
if (p -> next -> next == q) p = p -> next;
else p -> next = q;
}
return dummy -> next;
}
};