广州公司网站制作招聘信息,vi设计论文,网站企业地图,Wordpress怎么连接百度网盘在一个排序的链表中#xff0c;存在重复的节点#xff0c;请删除该链表中重复的节点#xff0c;重复的节点不保留。
数据范围 链表中节点 val 值取值范围 [0,100] 。 链表长度 [0,100] 。
样例1 输入#xff1a;1-2-3-3-4-4-5
输出#xff1a;…在一个排序的链表中存在重复的节点请删除该链表中重复的节点重复的节点不保留。
数据范围 链表中节点 val 值取值范围 [0,100] 。 链表长度 [0,100] 。
样例1 输入1-2-3-3-4-4-5
输出1-2-5 样例2 输入1-1-1-2-3
输出2-3
思想先定义一个虚拟节点防止头节点也被修改删除结果输出虚拟节点的next。然后定义一个指针从头开始遍历在每次遍历时先取q等于当前遍历节点的next然后寻找这一段相同数字的末尾比如1或者2,2并将q指向末位然后判断当前的q和p的next是否相同相同则说明一个值直接移动p否则删除这些重复的数字。 q就相当于一个侦察兵一直走到下一段数字的最后一个位置。
/*** 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 res new ListNode(-1);res-next head;auto p res;while(p-next) {auto q p-next;while(q-next q-val q-next-val) q q-next;if(q p-next) p q;else p-next q-next;}return res-next;}
};
