83. 删除排序链表中的重复元素_rena11的博客-爱代码爱编程
1.题目
给定一个已排序链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
2.示例
输入:head = [1,1,2]
输出:[1,2]
输入:head = [1,1,2,3,3]
输出:[1,2,3]
3.答案
注意: 链表已升序排列。 只用检查相邻元素是否重复,重复删除就可。
①递归
停止条件:链表为空或者只有一个元素
递归内容:链头之后结点删除重复值
返回值:返回新的头结点, 若头结点与下一结点重复,则返回下一节点,否则返回原头结点
ListNode* deleteDuplicates(ListNode* head) {
if(!head||!head->next) return head;
head->next=deleteDuplicates(head->next);
return head->val==head->next->val?head->next:head;
}
②迭代
双指针,不断检查相邻结点是否重复。
ListNode* reverseList(ListNode* head) {
if(!head||!head->next) return head;
ListNode *pre=head,*cur=head->next;
while(pre&&cur){
// cur重复,删除cur
if(pre->val==cur->val){
pre->next=cur->next;
cur=cur->next;
}else{
pre=pre->next;
cur=cur->next;
}
}
return head;
}