BM16 删除有序链表中重复的元素-II
删除有序链表中重复的元素-II
https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024?tpId=295&tqId=663&ru=%2Fpractice%2F71cef9f8b5564579bf7ed93fbe0b2024&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj
描述
给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1 \to 2\to 3\to 3\to 4\to 4\to51→2→3→3→4→4→5, 返回1\to 2\to51→2→5.
给出的链表为1\to1 \to 1\to 2 \to 31→1→1→2→3, 返回2\to 32→3.
例如：
给出的链表为1 \to 2\to 3\to 3\to 4\to 4\to51→2→3→3→4→4→5, 返回1\to 2\to51→2→5.
给出的链表为1\to1 \to 1\to 2 \to 31→1→1→2→3, 返回2\to 32→3.
数据范围：链表长度 0 \le n \le 100000≤n≤10000，链表中的值满足 |val| \le 1000∣val∣≤1000
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
这个题有点意思，逻辑也不复杂。
在之前的删除重复元素的题的基础上，增加了一个难度，是要删除所有的重复元素，而不是需要留下一个。
所以需要做一个标记。
满足这个标记的时候，在删除之前节点的基础上，直接删除当前的节点。
class Solution {
public:
/**
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* deleteDuplicates(ListNode* head) {
// write code here
ListNode *res = new ListNode(-1);
res->next = head;
ListNode *pre = res;
ListNode *cur = head;
while(cur && cur->next != NULL){
bool flag = false;
while(cur->next && cur->val == cur->next->val){
flag = true;
cur->next = cur->next->next;
}
if(flag){
pre->next = cur->next;
}else{
pre = cur;
}
cur = cur->next;
}
return res->next;
}
};
来吧，BAT 文章被收录于专栏
来吧，BAT
