首页 > 编程语言 >Java-数据结构-链表-习题(三)(๑´ㅂ`๑)

Java-数据结构-链表-习题(三)(๑´ㅂ`๑)

时间:2024-09-05 12:50:56浏览次数:13  
标签:head Java cur fast next 链表 ListNode 习题 节点

文本目录:

​❄️一、习题一:

    ▶ 思路:

  ▶ 代码:

​❄️二、习题二:

  ▶ 思路:

  ▶ 代码:

​❄️三、习题三:

  ▶ 思路:

  ▶ 代码:

​❄️四、习题四:

        ▶ 思路:

     ▶ 代码:

​❄️五、习题五:

  ▶ 思路:     

  ▶ 代码: 

 ​❄️六、习题六:

     ▶ 思路:

  ▶ 代码:

​❄️七、习题七:

     ▶ 思路:     

  ▶ 代码: 

​❄️总结:


❄️一、习题一:

☑ 题的链接:

     移除链表的元素

    ▶ 思路:

这个题呢,和我们在自实现单链表的时候呢,里面的删除所有的val这个值的节点的操作是类似的。我们在重新分析一下:

我们直接来看思路图:

  ▶ 代码:

OK,我们的这个题的思路已经分写完成了,接下来我们来看看代码如何实现的:

public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while(cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        //判断head的val是否和val相等
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

      这个呢就是我们这个题的代码了,是不是很简单呢?Ok,理解这个题目之后,我们接着往下看下一道题。


❄️二、习题二:

☑ 题的链接:

        翻转链表的OJ链接

  ▶ 思路:

在我们分析这个题的方法之前呢,我们先来看看其结果是什么: 

  那么我们这个操作是怎么做到的呢?我们来分析看看:

   我们的这个反转链表是不是相当于是头插呢?我们来看操作是不是定义一个节点用来存储 head 的下一个节点,这个节点就是要头插的节点当我们的 cur在 35 的时候,我们把 35 这个节点头插之后我们把 35 这个节点的 next 指向 head 这个节点,之后把 cur 这个节点设置为 head ,再继续 cur 往后走指向 45 这个节点,之后再进行头插并使 next 指向 head ,在设置head节点,重复这个操作,直至cur为空

    但是在这个操作中呢我们有几个要注意的点:

    1、我们在设置完cur之后呢,我们要把第一次的head节点置为 null ,因为当我们翻转之后呢原先的头会变成尾,所以要置null。

    2、我们在把cur节点头插之后呢,我们把cur的next指向head节点之后呢,我们就找不到原来cur的下一个节点了,所以我们要在头插之前就把cur的下一个节点存起来,防止丢失。

这样说呢,可能不够直观,我们来看看思路图,来更加直观的了解一下:

  ▶ 代码:

这个操作理解之后呢,我们来看看代码的实现: 

public ListNode reverseList(ListNode head) {
        //先判断链表是否为空
        if (head == null) {
            return head;
        }
        
        //开始头插
        ListNode cur = head.next;
        head.next = null; 
        while(cur != null) {
            //保存cur的下一个节点
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    OK,到这里呢,我们的第二题就已经结束了,让我们接着往下看下一题,这题是不是在理解之后就很简单了呢,如果不是很懂的话呢,也是可以画图理解一下。 


❄️三、习题三:

☑ 题的链接:

          链表的中间节点

    这个题用到的方法呢,是我们在做题的时候可能经常用到的方法:快慢指针法

  ▶ 思路:

    这个题呢,它的返回的节点 和链表的长度也是有关的当我们的节点个数为奇数的时候返回的就是中间节点;当我们的节点个数为偶数的时候,返回的是第二个中间节点

     我们来看看图片理解一下:

   那么这个操作我们有时怎样做到的呢?快慢指针又是怎样使用的呢? 

     这里呢,我们要设置两个节点,一个为slow ,一个为fast,之后呢我们要对这两个节点进行移动,我们fast节点每次移动两步,而我们的slow每次走一步当我们的fast走到null的时候呢,我们slow这个节点就到达了中间节点

    但是呢我们要注意的是:我们的 fast 的结束条件是不一样的,当我们的节点数为奇数的时候,我们 fast 的 next 为空时就是结束条件但当我们的节点个数为偶数的时候呢,当 fast 为空的时候就是结束条件

这样的理解可能不是很直观啊,我们还是再来看看其执行的思路图和结束时fast在哪:

我们先来看看奇数的情况下: 

我们再来看看偶数的情况下: 

  ▶ 代码:

我们偶数和奇数的情况都已经分析完事了,让我们来看看代码是如何编写的:

public ListNode middleNode(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        
        return slow;
    }

      这里我们还要注意的是,我们的 while 的判断条件中,fast 和 fast.next 的判断的先后顺序是不能改变的,如果改变了的话,假如我们的 fast 为 null 了之后,我们先访问 fast.next 的话,就会出现空指针异常。

  我们又结束了一道题目,我们还要继续往下看,我们来看下一道题: 


❄️四、习题四:

☑ 题的链接:

            返回倒数第k个节点

        ▶ 思路:

         这个题呢,我们用到的也是 快慢指针 的做法,但是呢这个题的快慢指针和上面的又是有所不同的,上面的快慢指针是fast 走2步,slow 走1步。这里呢,我们的做法呢,是先把 fast 走 k-1 步,之后再那 fast 和 slow一起走,直到 fast.next 为空的时候呢,slow 就是我们要返回的节点

         我们来看看思路图,来直观地了解一下:

        我们呢,这样看呢是不是发现我们 链表结尾和要返回的节点的距离 和 我们的一开始要设置的fast 和slow之间的距离是一样的。

     ▶ 代码:

      那么接下来我们来看看我们的这个题的代码是怎样写的:

public int kthToLast(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        
        while(k - 1 > 0) {
            fast = fast.next;
            k--;
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

   到这我们的这道题也结束了,让我们接着看下一道题:


❄️五、习题五:

☑ 题的链接:

            合并两个有序链表

  ▶ 思路:     

          对于这个题呢,我们呢要创建一个新的链表,因为这两个链表是有序地,所以呢我们呢可以对比两个链表的相对应位置的元素的大小,每次数值小的元素插入到新的链表当中,但是呢我们需要返回新链表的头结点,所以呢我们在插入之前呢我们需要先把新链表的位置保存下来,防止我们找不到头。但是我们要返回新链表的下一个节点,这才是我们的有效数据的节点。

  ▶ 代码: 

我们来看看这个题的代码如何编写:

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newList = new ListNode();
        ListNode prev = newList;
        while(list1 != null && list2 != null) {
            if (list2.val <= list1.val) {
                prev.next = list2;
                list2 = list2.next;
            }else {
                prev.next = list1;
                list1 = list1.next;
            }
            prev = prev.next;
        }
        if (list1 != null) {
            prev.next = list1;
        }
        if (list2 != null) {
            prev.next = list2;
        }

        return newList.next;
    }

  OK啊,我们呢这个题也完事了,我们接下来继续往下看下一题: 


 ❄️六、习题六:

☑ 题的链接:

          链表的分割

     ▶ 思路:

      这个题呢,在我们分析之前呢,我们先来看看这个题是什么意思: 

     这个题呢就是我们有一个 x 这个数值,当小于 x 的时候我们要把这个节点呢放到前面,而大于等于的呢放到后面,而且呢不能改变原来的数据顺序,我们来看表更直观的了解一下:

就是呢,这个意思。我们在来看看如何做这道题:

     我们这么分析,我们把小于 x 的 和 大于等于 x 的分成两个链表,一个呢放小于 x 的节点,另一个呢放大于等于 x 节点的数据 最后呢我们把小于 x 的链表的尾巴 和 大于 x 的链表的头连接在一起,再返回小于 x 链表的头。在返回之前呢我们要注意的是,我们的大于 x 的这个链表的尾巴节点不等于 null 的时候,我们要把其设置为null。我们来看看分析的思路图:

  ▶ 代码:

OK,我们分析完如何做呢,我们呢来看看代码是怎样实现的:

public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode smallHead = null;
        ListNode smallLast = null;
        ListNode bigHead = null;
        ListNode bigLast = null;
        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                if (smallHead == null) {
                    //第一次删除的时候
                    smallHead = smallLast = cur;
                } else {
                    smallLast.next = cur;
                    smallLast = smallLast.next;
                }
            } else {
                if (bigHead == null) {
                    bigHead = bigLast = cur;
                } else {
                    bigLast.next = cur;
                    bigLast = bigLast.next;
                }
            }
            cur = cur.next;
        }
        if (smallHead == null) {
            return bigHead;
        }
        smallLast.next = bigHead;
        if (bigLast != null) {
            bigLast.next = null;
        }
        return smallHead;
    }
}

OK了,这个题呢我们也完事呢,我们继续往下看下一道题: 


❄️七、习题七:

 ☑ 题的链接:

            链表的回文结构

     ▶ 思路:     

     这个题,我们还是请到我们的老朋友  快慢指针——双指针法 在分析这个题之间呢,我们先来看一下什么是 回文结构 :从前往后的结果和从后往前打印的结果是一样的,就是回文结构。比如我们来看这个图:

     这个呢就是 回文结构 从前往后是12->35->45->35->12 从后往前呢是 12->35->45->35->12 这就是回文结构了。 

      那么对于这个题呢,我们要怎样才能判断其链表是否是回文结构呢?我们呢对于这个题其实三步就可以了,第一:我们用双指针 fast 走2步 和 slow 走1步 来寻找中间节点,第二:再把中间节点后面的节点进行翻转,第三:在从头和从后面进行对比 val 值,每次都往前走一步进行对应位置的比较。我们来看看思路图是什么样的:

      是不是以为这样就结束了呢?当然不是了,我们在上面只是分析了奇数的情况下,但是呢我们没有分析偶数的情况下是什么样的。所以呢,我们再来看看偶数的情况下是什么样的:

  ▶ 代码: 

这样呢就把奇数和偶数的情况都分析完事了,之后我们来看看代码如何编写:

public boolean chkPalindrome(ListNode head) {
        //双指针法:快慢指针法
        if (head == null ) {
            return true;
        }
        //找中间节点,slow就是中间节点。
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //翻转中间节点后面的链表
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //判断是否回文
        while (head != slow) {
            if (head.val != slow.val) {
                return false;
            }
            //这里需要判断一下偶数的情况下
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

  这样呢,我们的这个回文结构的题呢,就结束了。 


❄️总结:

       OK啊,这次的对于链表的练习题就到这里就结束了,我们对于下次的分享呢,我们来分享关于栈的相关的知识了。希望这次的链表的习题对于你们有所帮助吧!!!让我们期待下次的见面吧,拜拜~~~

标签:head,Java,cur,fast,next,链表,ListNode,习题,节点
From: https://blog.csdn.net/2303_80388948/article/details/141872383

相关文章

  • 课题分享:校园闲置物品租售系统,基于java+springboot+mysql
      一、前言介绍        传统的校园闲置物品租售系统方式是在线下实体进行的,用户需要到线下进行实际的了解传统信息,而随着信息不断的普及,越来越多的校园商家也开始出于各种各样的理由而热衷网上发展,传统的线下模式已经无法满足人们的需求了。        互联......
  • 课题分享:校园闲置物品交易网站,基于java+springboot+mysql
      一、前言介绍        计算机的普及和互联网时代的到来使信息的发布和传播更加方便快捷。用户可以通过计算机上的浏览器访问多个应用系统,从中获取一些可以满足用户需求的管理系统。网站系统有时更像是一个大型“展示平台”,用户可以选择所需的信息进入系统查看首页......
  • Java基础语法
    Java基础语法1.注释​注释是对代码的解释和说明文字。Java中的注释分为三种:单行注释://这是单行注释文字多行注释:/*这是多行注释文字这是多行注释文字这是多行注释文字*/注意:多行注释不能嵌套使用。文档注释(暂时用不到):/**这是多行注释文字这是多行注释......
  • 课题分享:外卖点餐系统,基于java+springboot+mysql
      一、前言介绍        计算机的普及和互联网时代的到来使信息的发布和传播更加方便快捷。人们可以通过计算机上的浏览器访问多个应用系统,从中获取一些可以满足用户生活需求的管理系统。网站系统有时更像是一个大型“展示平台”,人们可以选择所需的信息进行在线下单......
  • Java接口使用指南:开启高效编程之门
    在Java编程世界中,接口是实现模块间通信的一种核心机制。它们定义了一组方法规范,允许不同的类或系统按照统一的方式进行交互。随着互联网服务的兴起,API(应用程序编程接口)成为了Java开发者必须掌握的技能之一。本文将为您详细介绍如何在Java中使用API接口,以及如何通过它们提升开发效......
  • Anylogic(2)——导出Java程序bat无法运行(Windows)
    1.Anylogic打包以后,双击bat,无论如何都无法运行。找了很多资料,最后得出可能是Java版本问题,因为最初安装anylogic的版本是8.9,Java安装得是1.8.x版本。改为安装Java9,但是依旧报错,也不知道具体,经痛苦多番挣扎,有2种情况。(报错如下)。 两种情况:①路径问题,因为某些时候Java......
  • 「Java开发指南」如何用MyEclipse搭建Adobe和Spring Flex?(一)
    本教程将引导您完成AdobeFlex和Spring-Flex软件组件的生成,可以生成一个随时可运行的SpringFlex应用程序,该应用程序为域模型实现了CRUD应用程序模式。在本教程中,您将学习如何:从数据库表搭建到现有项目设置关系获取类型更新Flex用户界面MyEclipsev2024.1离线版下载MyEclip......
  • Java箱与泛型
      大O的渐进表示法大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。voidfunc1(intN){intcount=0;for(inti=0;i<N;i++){for(intj=0;j<N;j++){count++;}}for(intk=0;k<2*N;k++){count++;}......
  • Java顺序表和链表万字详解
    1.线性表的概念线性表(linearlist)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列...线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,......
  • java07
    一、java包一个包(package)可以定义为一组相互联系的类型(类、接口、枚举和注释),为这些类型提供访问保护和命名空间管理的功能。(一)Java中的包:java.lang-打包基础的类java.io-包含输入输出功能的函数(二)创建包创建包的时候要为包取一个合适的名字如果其他的一个源文件包含了......