题目描述
在一个排序的链表中,存在重复的节点,请删除该链表中重复的节点,重复的节点不保留。
样例1
输入:1->2->3->3->4->4->5
输出:1->2->5
样例2
输入:1->1->1->2->3
输出:2->3
算法1
(不带头结点) $O(n)$
会稍微麻烦一点,算法中,如果有重复数,p指针指向的是重复数中的第一个,然后利用q指针删除其余重复的,
这样就只剩下p所指向的最后一个重复数,这时候可以利用在O(1)时间删除链表结点(参考https://www.acwing.com/problem/content/85/)
的操作来删除p所指结点。但这里有一类特殊情况要处理,当重复数出现在链表尾时,q指针最后会指向NULL,
所以需要特判一下!q,并且要区分整个链表都是重复数和仅表尾是重复数的情况。
s指向p的前去结点,当遇到特判时,s才发挥它的作用,s->next = NULL;
C++ 代码
class Solution {
public:
ListNode* deleteDuplication(ListNode* head) {
// 法1:不带头结点的算法
/*
会稍微麻烦一点,算法中,如果有重复数,p指针指向的是重复数中的第一个,然后利用q指针删除其余重复的,
这样就只剩下p所指向的最后一个重复数,这时候可以利用在O(1)时间删除链表结点(参考https://www.acwing.com/problem/content/85/)
的操作来删除p所指结点。但这里有一类特殊情况要处理,当重复数出现在链表尾时,q指针最后会指向NULL,
所以需要特判一下!q,并且要区分整个链表都是重复数和仅表尾是重复数的情况。
s指向p的前去结点,当遇到特判时,s才发挥它的作用,s->next = NULL;
*/
if (head != NULL)
{
// 1.在算法过程中,p指向第一个重复数,q负责重复数,s指向p的前驱结点
ListNode *p = head, *q = p->next, *s;
while (q != NULL)
{
bool d = false; // 2.判断p指向的是否是重复数
// 3.重复数,删除,直到不是重复数
while (q && p->val == q->val)
{
q = q->next;
p->next = q;
d = true;
}
if (!q) // 4.1 在链表表尾遇到重复数的处理语句
{
if (p == head) return NULL;
else s->next = NULL;
}
else if (d) // 4.2 删除最后一个重复数
{
// 在O(1)时间删除链表结点,参考https://www.acwing.com/problem/content/85/
p->val = q->val;
q = q->next;
p->next = q;
}
else // 4.3 不是重复数,跳到下一结点
s = p, p = q, q = p->next;
}
}
return head;
// 带头结点的算法
/*
yxc的解法,这里直接就省略了s指针,用指针p替代s,其余解题思路和法1差不多
为了方便处理边界情况,我们定义一个虚拟元素 dummydummy 指向链表头节点。
然后从前往后扫描整个链表,每次扫描元素相同的一段,如果这段中的元素个数多于1个,则将整段元素直接删除。
auto dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
while (p->next) {
auto 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;
*/
}
};