题目描述
给定一个有序链表，如果一个元素多余一个，则将该元素 全部删除，使得原链表只包含不同元素。
样例1
输入：1->2->3->3->4->4->5
输出：1->2->5
样例2
输入：1->1->1->2->3
输出：2->3
算法
(线性扫描) $O(n)$
为了方便处理边界情况，我们定义一个虚拟元素 $dummy$ 指向链表头节点。
然后从前往后扫描整个链表，每次扫描元素相同的一段，如果这段中的元素个数多于1个，则将整段元素直接删除。
时间复杂度分析：整个链表只扫描一遍，所以时间复杂度是 $O(n)$。
C++ 代码
/**
* 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) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* p = dummy;
while (p->next)
{
ListNode* q = p->next;
while (q && q->val == p->next->val)
q = q->next;
if (p->next->next == q) p = p->next;
else p->next = q;
}
return dummy->next;
}
};
这题也不好想呀，感觉~
为什么取名叫dummy？
个人理解dummy 一般是用来处理特殊情况的,比如头节点为空,或者进行一些操作后链表变为空,此时dummy->next仍然有效. 至于为什么叫dummy,可能是因为它不是一个真正的节点,习惯上叫dummy以和其它节点区分开.
class Solution {
public:
ListNode deleteDuplicates(ListNode head) {
if(!head||!head->next) return head;
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(head){
int flag = 0;
while(head->next&&head->val==head->next->val){
head = head->next;
flag=1;
}
if(flag){
cur->next = head->next;
}else{
cur->next = head;
}
head = head->next;
cur = cur->next;
}
return dummy->next;
}
};//为什么我这里会超时啊？