「双指针」删除排序链表中的重复元素 II(力扣第82题)

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

本题为1月15日力扣每日一题

题目来源:力扣第82题

题目tag:链表 双指针

题面

题目描述

给定一个已排序的链表的头head,删除原始链表中所有重复数字的节点,只留下不同的数字。返回已排序的链表。

示例

示例 1

输入:

head = [1,2,3,3,4,4,5]

输出:

[1,2,5]

示例 2

输入:

head = [1,1,1,2,3]

输出:

[2,3]

提示

链表中节点数目在范围$ [0,300] $内

$ -100 \leq Node.val \leq 100 $

题目数据保证链表已经按升序排列


思路分析

本题要做的其实就两件事,一是在链表中找到重复元素,二是删除链表的一些元素.

第一件事很好完成,只需要在编译时看一看当前元素和后一个元素的值是否相等即可.注意预防空指针.

对于第二件事,我们知道,删除链表中的一个元素,需要两个指针,一个指向要删除的元素,另一个指向删除元素的前驱元素(如果删除一连串元素,显然指向这一串元素中第一个元素的前驱元素).然后通过如下代码即可删除当前元素:

    prev->next = now->next;
    // 部分语言注意手动释放内存空间

如果你想不通上面的代码,这里简单解释一下.因为链表是通过next指针来确定前驱后继关系的,只要将当前元素从next指针链中移除即可,本题是单向链表,那么只需要把指向这个元素的指针移走,那么在next指针链中就找不到当前元素了,这样就完成了删除.

但是这样有一个问题,如果要删除的节点是整个链表的第一个节点呢?这样没有办法取得这个元素的前驱结点.这里有两个方法,一个是特判开头,把第一个不重复的元素作为头结点,无视前面的节点;另一个是构造一个虚拟的头结点,产生出第一个节点的前驱节点.此处出于个人习惯,采用第二种方式.实际上在其他涉及删除的问题中,构造虚拟头结点往往能大大简化分类讨论特判的过程.

由此,此题我们先构造一个虚拟的头结点,然后用两个指针来遍历这个链表.每次找到一串相同元素的最后一个元素,然后通过上面所说的方式将这一串连续的元素全部删除即可.

参考代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 创建虚拟头结点
        ListNode h(0, head);
        ListNode *prev = &h,*now = head;

        // 遍历整个链表
        while(now != nullptr && now->next != nullptr) {
            bool flag = false;

            // 找到该元素的最后一个
            while(now != nullptr && now->next != nullptr && now->val == now->next->val) {
                flag = true;
                ListNode *p = now;
                now = now->next;
                delete p; // 释放内存空间
            }

            if(flag) {
                // 出现重复,删掉所有重复的元素
                prev->next = now->next;
                ListNode *p = now;
                now = now->next;
                delete p; // 释放内存空间
            } else {
                // 没有重复,继续往后遍历
                prev = prev->next;
                now = now->next;
            }
        }
        // 返回时去掉头结点
        return h.next;
    }
};

"正是我们每天反复做的事情,最终造就了我们,优秀不是一种行为,而是一种习惯" ---亚里士多德文章来源地址https://www.toymoban.com/news/detail-790895.html

到了这里,关于「双指针」删除排序链表中的重复元素 II(力扣第82题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • ​LeetCode解法汇总82. 删除排序链表中的重复元素 II

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

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

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

    2024年02月12日
    浏览(58)
  • [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)
  • leetcode-删除排序链表中的重复元素

    83. 删除排序链表中的重复元素 题解: 要删除一个已排序链表中的所有重复元素,从而使每个元素只出现一次,我们可以使用一个指针来遍历这个链表,同时比较当前节点和它下一个节点的值。如果它们相等,我们就删除下一个节点,如果不相等,我们就移动指针。 注:本题

    2024年02月02日
    浏览(48)
  • LeetCode - #83 删除排序链表中的重复元素

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

    2024年02月10日
    浏览(44)
  • 【LeetCode】83. 删除排序链表中的重复元素

    思路 由于给定的链表是排好序的,因此重复的元素在链表中出现的位置是连续的,因此我们只需要对链表进行一次遍历,就可以删除重复的元素。 从指针 cur 指向链表的头节点,随后开始对链表进行遍历。如果当前 cur 与 cur.next 对应的元素相同,那么我们就将 cur.next 从链表

    2024年02月09日
    浏览(37)
  • LeetCode.82 删除排序链表中的重复元素 二

    LeetCode.82 删除排序链表中的重复元素 二 题目 思路: 1,提供的是无空头链表,需要加一个头结点来统一操作 2,使用三个工作指针 r:记录前一个节点,方便删除操作 p:记录此基准节点 q:前进节点 两种情况: 一 如果p与q不同,则p,q,r,均前进; 二 如果p与q相同,则q前进,

    2024年01月19日
    浏览(41)
  • Killing LeetCode [83] 删除排序链表中的重复元素

    给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 Ref Link:https://leetcode.cn/problems/remove-duplicates-from-sorted-list/ Difficulty:Easy Tag:LinkedList Updated Date:2023-08-02 示例1: 示例 2: 提示: 链表遍历 Accepted 复杂度分析 时间复杂度:

    2024年02月14日
    浏览(54)
  • leetcode做题笔记83删除排序链表中的重复元素

    给定一个已排序的链表的头  head  ,  删除所有重复的元素,使每个元素只出现一次  。返回  已排序的链表  。   本题与上题相似,但非将所有重复的元素删除,而是将多的重复元素删除,可添加判断语句判断前一个与后一个val值是否相等来决定是否放入链表中,最后输

    2024年02月12日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包