题目描述
在一个排序的链表中,存在重复的节点,请删除该链表中重复的节点,重复的节点不保留。
数据范围
链表中节点 val 值取值范围 [0,100]。
链表长度 [0,100]。
解题思路
如果需要从头开始遍历,并且第一个头节点也可能被删,引入头节点是一个很好的选择,首先按照创建节点的方式操作
即定义一个节点,让它的指针域指向下一个节点即head,然后给这个节点定义一个指针p用于标记
接着使用while循环遍历链节,给下一个节点做上标记q,方便测试一段的数值(相同的是排好的)
p储存要输出的链节,q标记下一段的第一个元素,如果相同就往下走,不相同就证明到下一段了
然后if条件句控制长度是否为1,如果是1的话p往后移一位(就是q的位置)得到答案,否则下一段大于1直接跳过删掉
注意,是直接删掉,通过p和q两个指针的操作会改变原来的连接关系,最后通过输出节点就可以输出改变后的所有链节
顺带🐎一个输出单个节点的方法:cout<<node.data<<endl;
(q指针的轨迹就是:2(生成)->3->4->4->5->5->null)
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) {
ListNode* virtu=new ListNode(-1);//创造虚拟节点
virtu->next=head; //virtu下一个节点是起始节点
ListNode* p=virtu; //给virtu加上一个指针
while(p->next){ //while循环遍历节点
ListNode* q=p->next; //给下一个节点加上一个指针q
while(q->next&&q->next->val==p->next->val){
q=q->next; //q一样的话往后走
}
if(q==p->next){
p=q; //返回输出值
}else{
p->next=q->next; //长度大于1直接删掉
}
}
return virtu->next; //返回修改以后的链节
}
};
篇章;
上一篇:AcWing 66. 两个链表的第一个公共结点
https://www.acwing.com/solution/content/212090/
下一篇:AcWing 67. 数字在排序数组中出现的次数
https://www.acwing.com/solution/content/212425/