删除有序链表中重复的元素-I
题目链接:删除有序链表中重复的元素-I
解题思路1:利用set
遍历链表,将元素放入set中,利用set中元素不重复的特点,相当于重复元素只保留了一份,最后再遍历set,重构删除重复元素后的链表
代码如下:文章来源地址https://www.toymoban.com/news/detail-626842.html
ListNode* deleteDuplicates(ListNode* head) {
set<int> s;
ListNode* cur = head;
while(cur != nullptr){
s.insert(cur->val);
cur = cur->next;
}
ListNode* res = new ListNode(-1);
cur = res;
for(auto const& e : s){
ListNode* temp = new ListNode(e);
cur->next = temp;
cur = cur->next;
}
return res->next;
}
解题思路2:遍历
如果下一个节点的值和本节点的值相同话,当前节点的下一个节点就指向next的next,如果不相同,就直接遍历下一个节点,注意cur = cur->next的位置,不能放在if语句外面,否则遇到连着几个相同值节点的时候,就会造成间隔删除,不符合题目要求
代码如下:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* cur = head;
while(cur != nullptr && cur->next != nullptr){
if(cur->next->val == cur->val){
cur->next = cur->next->next;
}else{
cur = cur->next;
}
}
return head;
}
解题思路3:递归
当前节点和下一个节点相同的时候,删除当前节点
代码如下:
ListNode* deleteDuplicates(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
head->next = deleteDuplicates(head->next);
if(head->next->val == head->val){
head = head->next;
}
return head;
}
删除有序链表中重复的元素-II
题目链接:删除有序链表中重复的元素-II
解题思路:借助map
遍历链表记录每个节点出现的次数,用map保存节点的值和出现次数,之后再遍历map,将出现次数为1的节点重建一条链表
代码如下:
ListNode* deleteDuplicates(ListNode* head) {
map<int, int> m;
ListNode* cur = head;
while (cur != nullptr) {
m[cur->val]++;
cur = cur->next;
}
ListNode* res = new ListNode(-1);
cur = res;
for (auto const& e : m) {
if (e.second == 1) {
ListNode* temp = new ListNode(e.first);
cur->next = temp;
cur = cur->next;
}
}
return res->next;
}
解题思路2:遍历
第一个while循环中cur->next != nullptr起到了两个关键作用是cur->next->next != nullptr不能替代的,首先是如果链表为空,那此时程序就可以直接返回了,还有一个是当cur到最后一个节点时,程序能正常退出
代码如下:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* res = new ListNode(-1);
res->next = head;
ListNode* cur = res;
while(cur->next != nullptr && cur->next->next != nullptr){
if(cur->next->val == cur->next->next->val){
int temp = cur->next->val;
while(cur->next != nullptr && cur->next->val == temp){
cur->next = cur->next->next;
}
}else{
cur = cur->next;
}
}
return res->next;
}
解题思路3:递归文章来源:https://www.toymoban.com/news/detail-626842.html
代码如下:
ListNode* deleteDuplicates(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
if(head->next!=nullptr && head->val==head->next->val){
while(head->next!=nullptr && head->val==head->next->val){
head->next = head->next->next;
}
head = deleteDuplicates(head->next);
}else{
head->next = deleteDuplicates(head->next);
}
return head;
}
到了这里,关于【题解】删除有序链表中重复的元素-I、II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!