算法-链表-简单-相交、反转、回文、环形、合并

记录一下算法题的学习5

在写关于链表的题目之前,我们应该熟悉回忆一下链表的具体内容

什么是链表:

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的地址。

怎么理解呢:是这样的:一个链表,一个结点除了要保存结点自身的值以外,还需要保存下一个结点的地址(指针或引用)

链表的分类:

单向链表和双向链表

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接。

  单向链表的节点有两个属性 val,next; val是当前节点的值,next是指向下一节点的指针或引用

一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接。

 链表常用的方法:

public void add(int index, E element)向指定位置插入元素。
public void addFirst(E e)头插法
public void addLast(E e)尾插法
public void clear()清空链表
public E remove(int index)删除指定位置元素
public boolean contains(Object o)判断是否含有某个元素
public E get(int index)返回指定位置的元素
public E set(int index, E element)返回指定位置的元素
public Object[] toArray()返回一个由链表组成的数组
public int indexOf(Object o)查找指定元素从前往后第一次出现的索引。

 

算法leetCode简单题目(单向链表)

相交链表:

题目:给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

代码与思路分析 

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         //LinkNode是JAVA中链表结点
         //创建一个哈希集合 为什么用hashSet,不用list,一个是不可重复元素,一个是可重复元素,
         Set<ListNode> select=new HashSet<ListNode>();
         //遍历链表headA将链表A中每个节点都加入哈希集合中
         ListNode node=headA;
         while(node!=null){
             select.add(node);//假设这是第一次将第一个节点加入哈希集合中
             node=node.next;//自动变为下一节点值
         }
         //遍历链表B,判断遍历到的每个节点,判断该节点是否在哈希集合中
         ListNode temp=headB;
         while(temp!=null){
             //contains() 方法用于判断元素是否在哈希集合中
           if(select.contains(temp)){
               return temp;
           }
           temp=temp.next;//自动变为下一节点值,进行遍历判断
         }
         //如果链表headB中的所有节点都不在哈希集合中,则两个链表不相交,返回null;
         return null;
    }
}

反转链表:

题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

代码与思路分析:

这个链表呢,是指向下一个节点的方向发生改变,使得链表发生了反转,下图便于理解分析:

 

 

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode original=head;//指向头结点
        ListNode end=null;  //指向null;
        //循环遍历使链表反转
        while(original!=null){
            ListNode temp=original.next; //使头结点的后继结点暂存,循环往复
            original.next=end; //改变next节点指向
            end=original;  //end暂存original
            original=temp;  //original往下一节点走
            
        }
        return end;
    }
}

回文链表:

题目:给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false

代码与思路分析:

首先我们要知道什么是回文即顺着看和倒着看是相同的

class Solution {
    public boolean  isPalindrome(ListNode head) {
      //我们的思路是将链表中的值复制到数组中,然后通过数组里使用左右双指针来判断是否回文
        //首先我们需要创建一个数组结构的集合,
        //使用单列集合Collection里的子接口List,它是有序且可重复元素
        List<Integer> vals=new ArrayList<Integer>();
        //其次将链表中的值复制到数组中,
        //单链表中的节点应该具有两个属性:val 和 next。
        // val 是当前节点的值,next 是指向下一个节点的指针/引用
        ListNode palindrome=head;
        while(palindrome!=null){
            vals.add(palindrome.val);//将回文链表中的每一个值复制到数组中,
            palindrome=palindrome.next;//指向下一个节点的指针/引用
        }
        //最后使用双指针判断是否回文
        int left=0; //List第一个元素的索引
        int right=vals.size()-1; //List最后一个元素的索引
        while(left<right){
            //两边发现值不相等,返回false
            if (!vals.get(left).equals(vals.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        //将元素全部跑一边,顺着和倒着是相同的,返回true
        return true;
    }
}

环形链表:

题目:

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

代码与思路分析:

我们重新作图使它更加直观:

 

 存储访问过的节点3 ,2,0,-4,然后我们又遇到了2这个节点,这个节点已经在哈希表中,所以证明该链表是一个环形链表。

public class Solution {
    public boolean hasCycle(ListNode head) {
        //首先创建一个哈希表,存储所有访问过的节点
        Set<ListNode>  node = new HashSet<ListNode>();
        //每当我们到达一个节点时,如果该节点已经存在于哈希表中,则说明该链表是环形链表,否则就将该节点加入哈希表中
        while(head!=null){
            if(!node.add(head)){
                return true;
            }
            //下一节点变化
            head=head.next;
        }
        //最后遍历完整个链表,发现不是环形链表,返回false;
        return false;
    }
}

合并两个有序链表:

题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

代码与思路分析:

如果 list1 或者 list2 本身就是空链表 ,那么我们就不需要合并,我们只需要返回非空链表。如果两个链表有一个为空,递归结束,因为另一个链表本身就是有序的。如果 list1 和 list2 都不是空链表,就要 判断 list1 和list2 哪一个链表的头节点的值更小,然后递归地决定下一个添加到新链表里的节点。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          //首先判断链表list1和链表list2是否是空联表,如果都是空的,返回就是[];
          if(list1==null){
              return list2;
          }
          if (list2==null){
              return list1;
          }
          //然后从最初开始的两个链表的头结点的值进行比较,哪个小,就排第一位,
          //紧接着有了合并链表的头结点之后,我们找该头结点的下一节点值。
        //这里就看list1和list2哪个链表的头结点先判断出来,然后使它成为新的合并有序链表之后的新链表
          if(list1.val<list2.val){
              list1.next=mergeTwoLists(list1.next,list2);
              return list1;
          }else{
              list2.next=mergeTwoLists(list1,list2.next);
              return list2;
          }
    }
}

结语:

链表的简单学习到此结束!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/155989.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Windows电脑画面如何投屏到电视?怎样限定投屏内容?

电视通常比计算机屏幕更大&#xff0c;因此将电脑画面投射到电视上可以提供更广阔的视野和更好的视觉体验。通过将电脑画面投射到电视上&#xff0c;您可以与他人共享您的计算机屏幕上的内容。这对于展示演示文稿、观看影片或与他人分享照片等活动非常有用。 如果你的电脑系统是…

Azure的AI使用-(语言检测、图像分析、图像文本识别)

1.语言检测 安装包&#xff1a; # 语言检测 %pip install azure-ai-textanalytics5.2.0 需要用到密钥和资源的终结点&#xff0c;所以去Azure上创建资源&#xff0c;我这个是创建好的了然后点击密钥和终结者去拿到key和终结点 两个密钥选择哪个都行 语言检测代码示例&#…

Vue数据绑定

在我们Vue当中有两种数据绑定的方法 1.单向绑定 2.双向绑定 让我为大家介绍一下吧&#xff01; 1、单向绑定(v-bind) 数据只能从data流向页面 举个例子&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"…

图论| 827. 最大人工岛 127. 单词接龙

827. 最大人工岛 题目&#xff1a;给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后&#xff0c;grid 中最大的岛屿面积是多少&#xff1f; 岛屿 由一组上、下、左、右四个方向相连的 1 形成。 题目链接&#xff1a;[827. 最大人工岛](ht…

佳易王麻将馆计时收费系统怎么安装,麻将馆的灯控什么原理?

佳易王麻将馆计时收费系统怎么安装&#xff0c;麻将馆的灯控什么原理&#xff1f; 佳易王计时计费软件只需将压缩包文件解压即可使用&#xff0c;灯控的原理是&#xff1a;软件在点击开始计时的时候&#xff0c;软件向灯控器发送开灯信号&#xff0c;相应的灯打开&#xff0c;…

【面试】测试/测开(未完成)

1. 黑盒测试方法 黑盒测试&#xff1a;关注的是软件功能的实现&#xff0c;关注功能实现是否满足需求&#xff0c;测试对象是基于需求规格说明书。 1&#xff09;等价类&#xff1a;有效等价类、无效等价类 2&#xff09;边界值 3&#xff09;因果图&#xff1a;不同的原因对应…

C/C+=内存管理

C/C内存管理以及动态内存的申请_c动态内存的申请与释放_Demo Test的博客-CSDN博客 问题是&#xff0c;这个0x0804 8000 到0xC 0000 0000之间&#xff0c;不止3GB&#xff0c;应该有47GB&#xff0c;该怎么解释呢&#xff1f;

【图像分类】【深度学习】【Pytorch版本】ResNet模型算法详解

【图像分类】【深度学习】【Pytorch版本】 ResNet模型算法详解 文章目录 【图像分类】【深度学习】【Pytorch版本】 ResNet模型算法详解前言ResNet讲解Deep residual learning framework(深度残差学习框架)ResNet残差结构ResNet模型结构 ResNet Pytorch代码完整代码总结 前言 …

深入探讨TensorFlow:张量与矩阵

在机器学习和深度学习领域中&#xff0c;TensorFlow作为一款强大且受欢迎的开源机器学习框架&#xff0c;为研究人员和开发者提供了丰富的工具和资源。在TensorFlow中&#xff0c;张量&#xff08;tensor&#xff09;和矩阵&#xff08;matrix&#xff09;是核心概念&#xff0…

Odoo 15开发手册第七章 记录集 - 使用模型数据

在前面的章节中&#xff0c;我们概览了模型创建以及如何向模型加载数据。现在我们已有数据模型和相关数据&#xff0c;是时候学习如何编程与其进行交互了。 业务应用需要业务逻辑来计算数据、执行验证或自动化操作。Odoo框架API为开发者提供了工具用于实现这种业务逻辑。大多数…

(二)什么是Vite——Vite 和 Webpack 区别(冷启动)

vite分享ppt&#xff0c;感兴趣的可以下载&#xff1a; ​​​​​​​Vite分享、原理介绍ppt 什么是vite系列目录&#xff1a; &#xff08;一&#xff09;什么是Vite——vite介绍与使用-CSDN博客 &#xff08;二&#xff09;什么是Vite——Vite 和 Webpack 区别&#xff0…

2018年五一杯数学建模C题江苏省本科教育质量综合评价解题全过程文档及程序

2019年五一杯数学建模 C题 江苏省本科教育质量综合评价 原题再现 随着中国的改革开放&#xff0c;国家的综合实力不断增强&#xff0c;中国高等教育发展整体已进入世界中上水平。作为一个教育大省&#xff0c;江苏省的本科教育发展在全国名列前茅&#xff0c;而江苏省13个地级…

【PB续命05】WinHttp.WinHttpRequest的介绍与使用

0 WinHttp.WinHttpRequest简介 winhttp.winhttprequest是Windows操作系统中的一个API函数&#xff0c;用于创建和发送HTTP请求。它可以用于从Web服务器获取数据&#xff0c;或将数据发送到Web服务器。该函数提供了许多选项&#xff0c;例如设置请求头、设置代理服务器、设置超…

花 200 元测试 1300 个实时数据同步任务

背景 对于将数据作为重要生产资料的公司来说&#xff0c;超大规模的数据迁移同步系统( 1k、5k、10k 条同步任务)是刚需。 本文以此为出发点&#xff0c;介绍近期 CloudCanal 所做的一个容量测试&#xff1a;在单个 CloudCanal 集群上创建 1300 实时任务&#xff0c;验证系统是…

2023年中国骨质疏松治疗仪发展趋势分析:小型且智能将成为产品优化方向[图]

骨质疏松治疗仪利用磁场镇静止痛、消肿消炎的治疗作用迅速缓解患者腰背疼痛等骨质疏松临床症状。同时利用磁场的磁-电效应产生的感生电势和感生电流&#xff0c;改善骨的代谢和骨重建&#xff0c;通过抑制破骨细胞、促进成骨细胞的活性来阻止骨量丢失、提高骨密度。 骨质疏松治…

【软件推荐】我的常用Windows软件

文章目录 前言Colors Lite&#xff08;颜色吸取&#xff09;Everything&#xff08;文件搜索&#xff09;知云文献翻译Directory Opus&#xff08;文件管理器&#xff09;Snipaste&#xff08;截图&#xff09;AxMath&#xff08;公式编辑器&#xff09;Deskpin&#xff08;窗口…

【Android】导入三方jar包/系统的framework.jar

1.Android.mk导包 1).jar包位置 与res和src同一级的libs中(没有就新建) 2).Android.mk文件 LOCAL_STATIC_ANDROID_LIBRARIES&#xff1a;android静态库&#xff0c;经常用于一些support的导包 LOCAL_JAVA_LIBRARIES&#xff1a;依赖的java库&#xff0c;一般为系统的jar…

Linux常用命令——bzcmp命令

在线Linux命令查询工具 bzcmp 比较两个压缩包中的文件 补充说明 bzcmp命令主要功能是在不真正解压缩.bz2压缩包的情况下&#xff0c;比较两个压缩包中的文件&#xff0c;省去了解压缩后在调用cmp命令的过程。 语法 bzcmp(参数)参数 文件1&#xff1a;指定要比较的第一个…

UE基础篇十:材质

导语: 视频文档在文末 虚幻引擎默认是延迟渲染(延迟渲染是通过先算出需要着色的像素,然后再迭代灯光,从而减少大量无效的灯光计算,来达到优化的目的) 一、基础知识 1.1 贴图分辨率尺寸 2的幂次方,长宽随意组合 非2的幂次方,不能设置MipMaps(引擎会生成多张分辨率更…

任务栏上的超萌小猫,实时显示CPU占用率,有趣.Net开源工具

推荐一个非常有趣的.Net开源小工具&#xff0c;它可以在电脑任务栏显示一只奔跑的小猫&#xff0c;实时显示CPU使用率&#xff01; 01 项目简介 一款基于.NET 6.0运行环境的开源小工具&#xff0c;通过它&#xff0c;用户可以直观地查看CPU的使用情况&#xff0c;它会根据 CP…