首页 > 其他分享 >【力扣】删除排序链表中的重复元素II

【力扣】删除排序链表中的重复元素II

时间:2024-02-24 23:45:06浏览次数:29  
标签:力扣 head ListNode cur slow2 fast next 链表 II

题目描述

image

思路

这些链表的有序性使这些操作都不难写。
前面在数组的题目里写过跳过重复元素的算法,这个和那个类似,用快慢指针写,但是由于这个是删除重复元素,所以我用了两个相邻的慢指针,左边的慢指针其实是为了保存真正的慢指针的上一个位置。
代码如下:

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == nullptr || head -> next == nullptr){
            return head;
        }
        ListNode* slow1 = new ListNode(-1,head);
        ListNode* slow2 = head;
        ListNode* fast = head;

        while(slow2!= nullptr){
            if(slow2 -> next != nullptr 
		&& slow2 -> val == slow2 -> next -> val){
		//发现了重复元素,开始使用fast指针跳过这些重复元素
                fast = slow2;
                while(fast != nullptr && 
			fast -> val == slow2 -> val){
                    fast = fast-> next;
                }
                if(slow2 == head){
                    head = fast;
                }
		//如果在开头删除了元素的话,需要更新head指针
                slow1 -> next = fast;
                slow2 = slow1 -> next;
                continue;
            }
            slow1 = slow1 -> next;
            slow2 = slow2 -> next;
        }
        return head;
    }
};

官方题解如下:

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) {
            return head;
        }
        
        ListNode* dummy = new ListNode(0, head);

        ListNode* cur = dummy;
        while (cur->next && cur->next->next) {
            if (cur->next->val == cur->next->next->val) {
                int x = cur->next->val;
                while (cur->next && cur->next->val == x) {
                    cur->next = cur->next->next;
                }
            }
            else {
                cur = cur->next;
            }
        }

        return dummy->next;
    }
};

解法大致一致,这种题也没有别的好方法,一般方法就是这种双指针。
但是它这个在空间上更优一点,它不是用两个相邻的慢指针,而是只用左边的慢指针,用到右边慢指针的时候都用next调用。

标签:力扣,head,ListNode,cur,slow2,fast,next,链表,II
From: https://www.cnblogs.com/satsuki26681534/p/18031812

相关文章

  • 代码随想录算法训练营第二十七天| 93.复原IP地址 78.子集 90.子集II
    复原IP地址 题目链接:93.复原IP地址-力扣(LeetCode)思路:投降。在判断字符串是否合法这部分遇到了困难。classSolution{private:vector<string>result;//记录结果//startIndex:搜索的起始位置,pointNum:添加逗点的数量voidbacktracking(string&s,int......
  • 【力扣】旋转链表
    题目描述思路首先用双指针法向后移动,分别获取链表的最后一个结点和倒数第k的结点,再把这部分连接到链表的头部即可,这部分的操作并不难。但是实际这样写了之后就会发现,如果链表的长度小于k的话,这样的操作就是行不通的,需要对这种情况进行特殊处理。但是在处理过程中发现这个操作......
  • 【力扣刷题】合并两个有序链表
    题目描述分析这道题实际的解法是要通过递归来写,由于链表的特性:链表的任何一个子表都是链表。所以很多链表的算法用递归来写会非常简便。这里先尝试着写一下非递归的算法,再写一遍递归的算法。非递归:classSolution{public://voidInsert(ListNode*node1,ListNode*n......
  • leedcode 杨辉三角-II
    自己写的:classSolution:defgetRow(self,rowIndex:int):#初始化一个列表以存储帕斯卡三角形的行li=[]#前两行是预定义的li.append([1])li.append([1,1])#rowIndex为0和1的基本情况ifrowIndex......
  • 基于sigma-delta和MASHIII调制器的频率合成器simulink建模与仿真
    1.算法运行效果图预览       其误差当系统进入稳定状态的时候,频率误差就小于1E-9,并且随着频率的增加,其稳定性将更好。 2.算法运行软件版本matlab2022a 3.算法理论概述       频率合成器是现代无线通信系统中的关键组件,用于生成精确且可调的频率信......
  • IIS PUT请求.netcore6.0接口 报HTTP Error 405 - Method Not Allowed
    在新的服务器上部署了一个.netcore的项目,部分请求地址使用了put、delete方式,导致无法正常请求,报Error405-MethodNotAllowed。由于配置IIS时把“WebDAV发布”给勾选了,所以会导致拦截。服务器和IIS10配置如下图:解决方案服务器上删除“WebDAV发布”1、打开“控制面......
  • 代码随想录算法训练营第二十七天 | 90.子集II , 78.子集, 93.复原IP地址
    93.复原IP地址 已解答中等 相关标签相关企业 有效IP地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。例如:"0.1.2.201" 和"192.168.1.1" 是 有效 IP地址,但是 "0.011.255.245"、"1......
  • 代码随想录算法训练营day03 | leetcode 203. 移除链表元素、707. 设计链表、206. 反转
    目录题目链接:203.移除链表元素-简单题目链接:707.设计链表-中等题目链接:206.反转链表-简单题目链接:203.移除链表元素-简单题目描述:给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。示例1:输入:head=[1,2,6......
  • 同一字母的大小写,ASCII码的低5位是相同的
    按键变更的次数【力扣周赛382】题目描述给你一个下标从0开始的字符串s,该字符串由用户输入。按键变更的定义是:使用与上次使用的按键不同的键。例如s="ab"表示按键变更一次,而s="bBBb"不存在按键变更。返回用户输入过程中按键变更的次数。注意:shift或capslock......
  • 代码随想录算法训练营第二十六天| 39. 组合总和 40.组合总和II 131.分割回文串
    组合总和题目链接:39.组合总和-力扣(LeetCode)思路:依然一是套用回溯模板,但是我们这里用回溯的是i而不是i+1,因为元素可以重复使用,注意for循环里if(sum(path)<=target)的等号不能少。classSolution{public:vector<int>path;vector<vector<int>>result;intsu......