学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

2024-09-09 04:28

本文主要是介绍学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 删除排序链表中的重复元素
      • 我的思路
        • 解法一:循环
        • 解法二:递归
      • 网上思路
    • 删除排序链表中的重复元素 II
      • 我的思路
      • 网上思路
    • 总结

删除排序链表中的重复元素

给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。

图一
在这里插入图片描述

图二
在这里插入图片描述

示例 1:(图一)
输入:head = [1,1,2]
输出:[1,2]示例 2:(图二)
输入:head = [1,1,2,3,3]
输出:[1,2,3]

我的思路
两个思路,一个是循环,一个是递归
网上思路
双指针

我的思路

解法一:循环
var deleteDuplicates = function(head) {let current = head;while (current && current.next) {if (current.val === current.next.val) {current.next = current.next.next; } else {current = current.next;}}return head;
};

讲解

  1. 初始化指针:创建一个指针 current 指向链表的头节点。
  2. 遍历链表:遍历链表直到 current.next 为空。
  3. 检查重复:如果当前节点 current 的值与下一个节点 current.next 的值相同,则跳过下一个节点,即将 current.next 设置为 current.next.next
  4. 继续遍历:如果当前节点 current 的值与下一个节点 current.next 的值不同,则将 current 指针移动到下一个节点。
  5. 返回结果:遍历完成后返回链表的头节点。
解法二:递归
var deleteDuplicates = function (head) {if (head === null || head.next === null) return head;if (head.next.val === head.val) {head.next = head.next.next;return deleteDuplicates(head);} else {head.next = deleteDuplicates(head.next);return head;}
};

讲解

  1. 如果链表为空(head === null) 或只有一个节点 (head.next === null),则返回头节点,因为没有重复节点需要删除。
  2. 如果当前节点的值与下一个节点的值相同**(head.next.val === head.val)**,则说明存在重复节点。
  3. 通过 head.next = head.next.next,我们将当前节点的 next 指向下一个节点的下一个节点,从而跳过了重复节点。
  4. 然后递归调用 deleteDuplicates(head),继续检查当前节点**(head)**的下一个节点。
  5. 如果当前节点的值与下一个节点的值不相同,说明没有重复节点。
  6. 递归调用 deleteDuplicates(head.next) 处理下一个节点,并将返回的结果赋值给 head.next,以确保链表的结构保持正确。

网上思路

var deleteDuplicates = function (head) {if (!head) return head;let prev = head;let current = head.next;while (current) {if (current.val === prev.val) {prev.next = current.next;} else {prev = current;}current = current.next;}return head;
};

讲解

  1. 初始化指针:
    prev 指向链表的头节点。
    current 指向头节点的下一个节点。
  2. 遍历链表:
    使用 while (current) 来遍历整个链表
  3. 检查重复:
    如果 current.val 和 prev.val 相同,说明存在重复。
    prev.next = current.next:通过调整 prevnext 指针,跳过重复的节点。
  4. 移动指针:
    如果当前节点和前一个节点的值不同,则移动 prev 指针到当前节点。
    无论是否有重复,current 指针始终向前移动。

删除排序链表中的重复元素 II

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

图三
在这里插入图片描述

图四
在这里插入图片描述

示例 1:(图三)
输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]示例 2:(图四)
输入:head = [1,1,1,2,3]
输出:[2,3]

我的思路
双指针
网上思路
递归

我的思路

var deleteDuplicates = function (head) {let dummy = new ListNode(0, head);let prev = dummy;let curr = head;while (curr && curr.next) {if (curr.val === curr.next.val) {while (curr.next && curr.val === curr.next.val) {curr = curr.next;}prev.next = curr.next;} else {prev = prev.next;}curr = curr.next;}return dummy.next;
};

讲解

  1. 创建哑节点:为了方便处理头节点可能被删除的情况,我们可以在链表前面添加一个哑节点。
  2. 初始化指针:创建一个指针 prev 指向哑节点,创建一个指针 curr 指向链表的头节点。
  3. 遍历链表:遍历链表直到 curr 到达末尾。
  4. 检查重复:如果当前节点 curr 的值与下一个节点 curr.next 的值相同,则继续向前遍历直到找到一个不同的节点。
  5. 连接不同节点:一旦找到不同的节点,将 prev.next 设置为这个不同的节点。
  6. 更新指针:如果没有重复节点,则将 prevcurr 都移动到下一个节点。
  7. 返回结果:遍历完成后返回哑节点的下一个节点作为新的头节点。

网上思路

var deleteDuplicates = function (head) {if (!head || !head.next) return headif (head.val === head.next.val) {while (head.next && head.next.val === head.val) head.next = head.next.nextreturn deleteDuplicates(head.next)} else {head.next = deleteDuplicates(head.next)}return head
};

讲解

  1. 基本情况检查:
    if (!head || !head.next) return head:如果链表为空**(head 为 null)或者只有一个节点(head.next 为 null)**,则直接返回 head。这是递归的基本情况,表示链表已经处理完成。
  2. 检查当前节点与下一个节点的值:
    if (head.val === head.next.val):检查当前节点的值是否与下一个节点的值相同。如果相同,说明存在重复节点。
  3. 跳过重复节点:
    while (head.next && head.next.val === head.val) head.next = head.next.next:使用 while 循环,继续跳过所有与当前节点值相同的节点, 直到找到一个不同的节点或到达链表末尾。
  4. 递归调用:
    return deleteDuplicates(head.next):在跳过所有重复节点后,递归调用 deleteDuplicates 处理下一个节点,并返回处理后的链表。
  5. 处理不同的节点:
    else { head.next = deleteDuplicates(head.next) }:如果当前节点的值与下一个节点的值不同,递归调用 deleteDuplicates 处理下一个节点,并将返回的结果赋值给 head.next
  6. 返回处理后的头节点:
    return head:最后,返回处理后的链表头节点。

总结

链表的题目写了这么多天,好像都可以用递归来解题,今天尝试了一下,还是不错的,后面可以再多尝试尝试。

这篇关于学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1150154

相关文章

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

SQL Server清除日志文件ERRORLOG和删除tempdb.mdf

《SQLServer清除日志文件ERRORLOG和删除tempdb.mdf》数据库再使用一段时间后,日志文件会增大,特别是在磁盘容量不足的情况下,更是需要缩减,以下为缩减方法:如果可以停止SQLSe... 目录缩减 ERRORLOG 文件(停止服务后)停止 SQL Server 服务:找到错误日志文件:删除

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定

mysql删除无用用户的方法实现

《mysql删除无用用户的方法实现》本文主要介绍了mysql删除无用用户的方法实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 1、删除不用的账户(1) 查看当前已存在账户mysql> select user,host,pa

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快