【题解】删除有序链表中重复的元素-I、II

这篇具有很好参考价值的文章主要介绍了【题解】删除有序链表中重复的元素-I、II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

删除有序链表中重复的元素-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:递归

代码如下:

    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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode——82. 删除排序链表中的重复元素II

    通过万岁!!! 题目:题目的大致意思就是,给你一个升序的链表,然后让你里面的元素有重复的,所有重复的元素都进行一个删除。 思路:这个题的简化版是“83.删除排序链表中的重复元素”。看到链表的题目可以优先考虑一下双指针。这里因为head也有可能跟下面的重复

    2024年01月16日
    浏览(46)
  • LeetCode - #82 删除排序链表中的重复元素 II

    我们社区陆续会将顾毅( Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。 )的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 LeetCode 算法到目前我们已经更新了 82 期,我们会保持更新时间和进度( 周一、周三、周五早上 9:00 发布 ),每期的内容不多,

    2024年02月10日
    浏览(35)
  • 【面试必刷TOP101】面试官:如何删除有序链表中重复的元素?

    🍳作者: 贤蛋大眼萌,一名很普通但不想普通的程序媛 color{#FF0000}{贤蛋 大眼萌 ,一名很普通但不想普通的程序媛} 贤蛋大眼萌,一名很普通但不想普通的程序媛 🤳 🙊语录: 多一些不为什么的坚持 color{#0000FF}{多一些不为什么的坚持} 多一些不为什么的坚持 📓 专栏:牛

    2024年01月23日
    浏览(46)
  • ​LeetCode解法汇总82. 删除排序链表中的重复元素 II

    https://github.com/September26/java-algorithms 给定一个已排序的链表的头  head  ,  删除原始链表中所有重复数字的节点,只留下不同的数字  。返回  已排序的链表  。 示例 1: 示例 2: 提示: 链表中节点数目在范围  [0, 300]  内 -100 = Node.val = 100 题目数据保证链表已经按升序  排

    2024年01月17日
    浏览(44)
  • 「双指针」删除排序链表中的重复元素 II(力扣第82题)

    本题为1月15日力扣每日一题 题目来源:力扣第82题 题目tag: 链表 双指针 给定一个已排序的链表的头head,删除原始链表中所有重复数字的节点,只留下不同的数字。返回已排序的链表。 示例 1 输入: 输出: 示例 2 输入: 输出: 链表中节点数目在范围$ [0,300] $内 $ -100 leq Nod

    2024年02月01日
    浏览(49)
  • leetcode做题笔记82删除排序链表中的重复元素 II

    给定一个已排序的链表的头  head  ,  删除原始链表中所有重复数字的节点,只留下不同的数字  。返回  已排序的链表  。 本题将重复的元素全部删除,可以考虑新建一个链表,若有重复元素则不放入新链表中,最后输出新链表即可。链表操作需要用另一个链表记录原来

    2024年02月12日
    浏览(58)
  • Leetcode刷题笔记题解(C++):83. 删除排序链表中的重复元素

    思路:链表相关的问题建议就是画图去解决,虽然理解起来很容易,但就是写代码写不出来有时候,依次去遍历第二节点如果与前一个节点相等则跳过,不相等则遍历第三个节点

    2024年02月22日
    浏览(63)
  • [M链表] lc82. 删除排序链表中的重复元素 II(单链表+好题+模拟)

    链接:82. 删除排序链表中的重复元素 II 相似题目:[E链表] lc83. 删除排序链表中的重复元素(单链表+模拟) 这个题目与 83 题都很类似,一个是将重复元素全部删除,另一个是将重复元素至多保留一个。注意以下几点即可: 本题可能一个节点都不存在,且头结点也可能被删除发

    2024年01月15日
    浏览(58)
  • 算法leetcode|82. 删除排序链表中的重复元素 II(rust重拳出击)

    给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。 链表中节点数目在范围 [0, 300] 内 -100 = Node.val = 100 题目数据保证链表已经按升序 排列 面对这道算法题目,二当家的再次陷入了沉思。 这道题目和 83. 删除排序

    2024年02月08日
    浏览(36)
  • 题解 | #删除链表中重复的结点#(哈希表)

    发现《剑指offer》里很多的链表题都是需要用到各种模板类,哈希模板类是高频出现的内容,学校里教到STL基本的类就结束了,甚至连vector这类神器都是一笔带过。。 话不多说,上代码 这题的核心思路就是利用哈希表中,可以使用值去查找内容的特性来找。 实际上大一刷A

    2024年02月12日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包