[AcWing 29] 删除链表中重复的节点
2024-08-27 21:40:58
点击查看代码
/**
* 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;
else p->next = q;
}
return dummy->next;
}
};
- 使用虚拟头结点便于处理头结点的各种情况;
- p 指向新链表的尾结点,q 指向 p 的下一个结点,while(q && p->next->val == q->val) 至少会执行一次(因为 q = p->next),下面分两种情况讨论:
① 若 p->next 结点是不重复的结点,即 p->next->next == q,则把 p 后移一位,把 p->next 加到新链表中;
② 若 p->next 结点是重复的结点,则此时 q 指向的是 q->val != p->next->val 的第一个结点(q 有可能和 q 后面的重复),此时执行 p->next = q,跳过刚刚重复的那段,p->next 此时指向的是一个新的结点,再判断此结点是否重复;
最新文章
- Python 3.4 send mail
- 采用flask+uwsgi+nginx架构将flask应用程序部署在腾讯云
- (原创)如何使用selenium 驱动chrome浏览器并且打开方式为手机模式-转载请注明出处
- C#集合 -- Equality和Order插件
- Nhibernate中CreateSQLQuery用法实例
- ImportError: No module named _winreg
- RAC 之 RMAN 恢复
- 使用pypi镜像源加速第三方库在线安装
- HDU-1339 A Simple Task
- 关于Java集合的总结
- Android入门第十六篇之Style与Theme [转]
- hdu_5964:平行四边形
- PostgreSQL存储过程(3)-流程控制语句
- C++初学 virtual 相关
- javaScript补充
- IntelliJ IDEA~gradle环境配置
- 面试题之python基础
- (6)Jquery1.8.3快速入门_过滤选择器
- AI 概率图模型
- 理解WebSocket心跳及重连机制(五)