题目描述
在一个排序的链表中,存在重复的节点,请删除该链表中重复的节点,重复的节点不保留。
数据范围
链表中节点 val 值取值范围 [0,100]。
链表长度 [0,100]。
样例
输入:1->2->3->3->4->4->5
输出:1->2->5
输入:1->1->1->2->3
输出:2->3
算法1
凡是可能把头节点删掉的问题,都要定义一个虚拟头节点,来简化代码
dummy的好处:新加入头节点,保证头节点一定不会被删掉
算法流程 $O(n^2)$
将取值相同的节点看作一段
p:上一次保留节点的最后一个
q:扫描下一段
判断下一段长度是否为1:p->next->next = q
时间复杂度 $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* deleteDuplication(ListNode* head) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy; //记录上次保留节点的结尾
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; //下一段长度为1
else
p->next = q;
}
return dummy->next;
}
};
总结
学习的点
1. dummy的使用
2. 怎么判断出现重复(上次的下下个 == 这次的下个)