【LeetCode每日一题】83. 删除排序链表中的重复元素
【LeetCode每日一题】83. 删除排序链表中的重复元素
公众号guangcity
发布于 2021-03-30 14:42:24
发布于 2021-03-30 14:42:24
【LeetCode每日一题】83. 删除排序链表中的重复元素
今天开始打卡LeetCode每日一题，今天题目比较简单，就是删除链表中的重复结点。
注意：是升序链表
思路有三个，第一个是迭代中删除结点，第二个是递归法，第三个是把所有结点存起来(去重)，重新构建。
第三个就不推荐了，就写了前两个方法。
解法1： 迭代法，判断无结点 or 1个结点情况，直接返回；其次，考虑一般情况，a结点标记当前第一个新结点，b结点表示下一个新结点，那么a->next=b便是无重复链表。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !head->next) return head;
ListNode* a = head, *b = head->next;
while(b) {
auto c = b->next;
if (a->val == b->val) {
delete b;
} else {
a->next = b; // find
a = b;
}
b = c;
}
a->next = nullptr;
return head;
}
};
解法2： 递归法，假设后面是已经无重复的链表，1->2->3，那么当前链表无非下面两种情况：
- 情况1：1->1->2->3
- 情况2：0->1->2->3
情况1表示当前结点跟递归的结点是重复的，那么直接断开连接并返回递归的结点即可；第二种情况就是正常的，正常连接当前结点与递归结点，返回正常结点作为头节点即可。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !head->next) return head;
ListNode* newHead = deleteDuplicates(head->next);
if (head->val == newHead->val) {
head->next = nullptr;
return newHead;
} else {
head->next = newHead;
return head;
}
}
};
本节完
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-03-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录