无头单向非循环链表实现 and leetcode刷题

无头单向非循环链表实现

  • 1. 单链表的模拟实现
    • IList.java接口：
    • MySingleList.java文件：
  • 2. leetcode刷题
    • 2.1 获取链表的中间节点
    • 2.2 删除链表中所有值为value的元素
    • 2.3 单链表的逆置
    • 2.4 获取链表倒数第k个节点
    • 2.5 给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式
    • 2.6 判定链表是否是回文
    • 2.7 判定链表相交并求出交点
    • 2.8 判断链表带环
    • 2.9 求环的入口点
    • 2.10 合并两个有序链表

写在最前面，学习数据结构一定要结合画图！先画图分析，写出伪代码，再仔细分析伪代码是否成立，成立再写入题目中检验！

1. 单链表的模拟实现

单链表的模拟实现需要创建三个文件：IList.java接口文件，MySingleList.java文件，还有一个test.java测试文件。测试文件这里就不演示了。

IList.java接口：

public interface IList {// 1、无头单向非循环链表实现//头插法void addFirst(int data);//尾插法void addLast(int data);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();void clear();void display();
}

MySingleList.java文件：

public class MySingleList implements IList{static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public void creatList() {ListNode node1 = new ListNode(0);ListNode node2 = new ListNode(1);ListNode node3 = new ListNode(2);ListNode node4 = new ListNode(3);node1.next = node2;node2.next = node3;node3.next = node4;head = node1;}@Overridepublic void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}@Overridepublic void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;}@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null) {head = node;return;}//找尾ListNode cur = head;while(cur.next != null) {cur = cur.next;}cur.next = node;}@Overridepublic void addIndex(int index, int data) {if(index < 0 || index > size()) {System.out.println("index位置不合法！");return;}if(index == 0) {addFirst(data);return;}if(index == size()){addLast(data);return;}ListNode node = new ListNode(data);ListNode cur = head;for (int i = 0; i < index-1; i++) {cur = cur.next;}node.next = cur.next;cur.next = node;}@Overridepublic boolean contains(int key) {ListNode cur = head;while(cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {if(head == null) {return;}if(head.val == key) {head = head.next;return;}ListNode pre = head;while(pre.next != null) {if(pre.next.val == key) {ListNode del = pre.next;pre.next =del.next;return;}pre = pre.next;}}@Overridepublic void removeAllKey(int key) {if(head == null) {return;}ListNode pre = head;ListNode cur = head.next;while(cur != null) {if(cur.val == key) {pre.next = cur.next;}else {pre = cur;}cur = cur.next;}//该if语句只能放在最后面，如果头节点需要删除，//删除后有可能下一个节点（此时这个节点做头节点）依然是需要删除的//因此，只能放在最后，当后面的都删除好了，再检查头节点是否需要删除if(head.val == key) {head = head.next;}}@Overridepublic int size() {int len = 0;ListNode cur = head;while(cur != null) {cur = cur.next;len++;}return len;}@Overridepublic void clear() {head = null;}
}

2. leetcode刷题

2.1 获取链表的中间节点

题目链接：876. 链表的中间结点

注意：题目中说明当链表只有一个中间结点时，返回该节点；而当该链表有两个中间结点，返回第二个结点

解析：定义一对“快慢指针”，“快指针”为fast，一次走两步；“慢指针”为slow，一次走一步。

  • 当链表的结点个数为奇数个时，fast走到fast.next == null时，slow此时所在位置就是中间节点
  • 当链表的节点个数为偶数个时，fast走到fast == null时，slow此时所在位置就是中间节点

代码如下：

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

2.2 删除链表中所有值为value的元素

题目链接：203. 移除链表元素

这题的题解和模拟实现单链表的removeAllKey是一样的，故不再赘述。

代码如下：

class Solution {public ListNode removeElements(ListNode head, int val) {if(head == null) {return head;}ListNode pre = head;ListNode cur = head.next;while(cur != null) {if(cur.val == val) {pre.next = cur.next;}else {pre = cur;}cur = cur.next;}if(head.val == val) {head = head.next;}return head;}
}

2.3 单链表的逆置

题目链接：206. 反转链表

解析：只需将链表的每个箭头调转方向即可，即修改当前节点的next值为前一个节点的地址，修改后就无法获取下一个节点了，故需要一个curN来定位下一个节点，又由于是单链表，无法得到前一个节点的位置，所以还需要定义一个prev来定位前一个节点的位置

在这里插入图片描述
代码如下：

class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null) {return head;}ListNode pre = head;ListNode cur = head.next;ListNode curN = head.next.next;pre.next = null;while(cur != null) {cur.next = pre;pre = cur;cur = curN;if(curN != null) {curN = curN.next;}}return pre;}
}

2.4 获取链表倒数第k个节点

题目链接：面试题 02.02. 返回倒数第 k 个节点

解析：定义一对“快慢指针”，”快指针“fast先走k步，然后”快指针“fast和”慢指针“slow一起一次走一步，直至fast == null结束，这时slow指向的便是倒数第k个节点

代码如下：

class Solution {public int kthToLast(ListNode head, int k) {if(head == null) {return -1;}ListNode fast = head;ListNode slow = head;for(int i = 0; i < k; i++) {fast = fast.next;}while(fast != null) {fast = fast.next;slow = slow.next;}return slow.val;}
}

2.5 给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式

题目链接：CM11 链表分割

注意：这题是将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序

public class Partition {public ListNode partition(ListNode head, int x) {// write code hereif(head == null) {return null;}ListNode bs = null;//bs:beforestartListNode be = null;//be:beforeendListNode as = null;//as:afterstartListNode ae = null;//ae:afterendListNode cur = head;while(cur != null) {if(cur.val < x) {if(bs == null) {//找到bs和be的起始位置bs = be = cur;}else {be.next = cur;be = cur;}}else {if(as == null) {//找到as和ae的起始位置as = ae = cur;}else {ae.next = cur;ae = cur;}}cur = cur.next;}//ae的next需要手动置为nullif(ae != null) {ae.next = null;}//如果链表的节点都大于x，则返回asif(bs == null) {return as;}//bs不为null，be自然也不为空be.next = as;return bs;}
}

2.6 判定链表是否是回文

题目链接：OR36 链表的回文结构

public class PalindromeList {public boolean chkPalindrome(ListNode A) {// write code hereif(A == null) {return false;}if(A.next == null) {return true;}//1.找到中间节点ListNode mid = getMiddleNode(A);//2.反转后半部分ListNode as = reseverList(mid);mid.next = null;//一定要置null！//3.从前往后依次对比两个链表的val值是否相同ListNode bs = A;while(bs.next != null && as.next != null) {if(bs.val != as.val) {return false;}bs = bs.next;as = as.next;}if(bs.val != as.val) {return false;}return true;}private ListNode reseverList(ListNode head) {ListNode prev = head;ListNode cur = head.next;ListNode curN = cur.next;while(cur != null) {cur.next = prev;prev = cur;cur = curN;if(curN != null){curN = curN.next;}}return prev;}private ListNode getMiddleNode(ListNode A) {ListNode fast = A;ListNode slow = A;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}return slow;}
}

2.7 判定链表相交并求出交点

题目链接：160. 相交链表

解题思路：

  1. 分别求出两个链表的长度，并得到两链表的长度差值（正数）
  2. 先让长链表的“l指针”走长度差值步，再让“l指针”和“s指针”一起走，如果相遇，相遇点即为相交链表的交点，如果没有相遇，则最后l和s同时为null
  3. 检验当两个链表同时为null时，代码是否满足

代码如下：

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int lenA = size(headA);int lenB = size(headB);//先假设headA链表的长度大于headB链表ListNode l = headA;ListNode s = headB;int len = lenA-lenB;//如果是headB链表更长，则进入if语句，进行调换if(len < 0) {len = -len;l = headB;s = headA;}for(int i = 0; i < len; i++) {l = l.next;}while(l != s) {l = l.next;s = s.next;}if(l == null) {return null;//没相交}return l;}public int size(ListNode head) {int len = 0;ListNode cur = head;while(cur != null) {cur = cur.next;len++;}return len;}
}

2.8 判断链表带环

题目链接：141. 环形链表

解题思路：

  1. 定义一对“快慢指针”，快指针fast一次走两步，慢指针slow一次走一步
  2. 如果最后fast == slow，则说明该链表存在环形结构；如果最后 fast == null || fast.next == null，则说明该链表不存在环形结构
  3. 检验链表为null时，代码是否满足

代码如下：

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if(fast == slow) {return true;}}return false;}
}

2.9 求环的入口点

题目链接：142. 环形链表 II

解题思路：

  1. 先判断链表结构中是否存在环（在2.8代码中进行略微修改即可）
  2. 求交点: 让一个引用从链表起始位置开始，一个引用从相遇点位置开始，两个引用每次都走一步，最终相遇时的节点即为交点（原因如下）

数学推导：
在这里插入图片描述
代码如下：

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;//这个if语句必须放在下面，否则该if语句第一次就会成立，//因为fast和slow第一次都是headif(fast == slow){break;}}if(fast == null || fast.next == null) {return null;}slow = head;while(fast != slow) {fast = fast.next;slow = slow.next;}return fast;}
}

2.10 合并两个有序链表

题目链接：21. 合并两个有序链表

解题思路：

  1. 创建一个带头结点的单链表
  2. 依次对比两个链表的数值大小，小的尾插到新链表尾部
  3. 当一个链表被新链表连接完时，另一个链表剩下的部分直接尾插到新链表的尾部
  4. 检验当一个链表为null时，代码是否满足

代码如下：

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode cur1 = list1;ListNode cur2 = list2;ListNode newHead = new ListNode();//NewHead为带头结点ListNode curN = newHead;while(cur1 != null && cur2 != null) {if(cur1.val < cur2.val) {curN.next = cur1;cur1 = cur1.next;} else {curN.next = cur2;cur2 = cur2.next;}curN = curN.next;}if(cur1 == null) {curN.next = cur2;}if(cur2 == null) {curN.next = cur1;}return newHead.next;}
}

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

java使用easypoi模版导出word详细步骤

java使用easypoi模版导出word详细步骤

文章目录 第一步、引入pom依赖第二步、新建导出工具类WordUtil第三步、创建模版word4.编写接口代码5.导出结果示例 第一步、引入pom依赖 <dependency><groupId>cn.afterturn</groupId><artifactId>easypoi-spring-boot-starter</artifactId><…
阅读更多...
AutoMQ vs Kafka: 来自小红书的独立深度评测与对比

AutoMQ vs Kafka: 来自小红书的独立深度评测与对比

测试背景 当前小红书消息引擎团队与 AutoMQ 团队正在深度合作&#xff0c;共同推动社区建设&#xff0c;探索云原生消息引擎的前沿技术。本文基于 OpenMessaging 框架&#xff0c;对 AutoMQ 进行了全面测评。欢迎大家参与社区并分享测评体验。 01 测试结论 本文主要测评云…
阅读更多...
Elon Musk开源Grok

Elon Musk开源Grok

转载自&#xff1a;AILab基地 早在6天前&#xff0c;马斯克就发文称xAI将开源Grok 图片 13小时前&#xff0c;马斯克开源了旗下公司X的Grok训练模型&#xff0c;并喊话OpenAI&#xff0c;你名字里的Open到底在哪里 图片 下面是xai-org的GitHub开源地址[https://github.com/x…
阅读更多...
yolov8、RTDETR无法使用多个GPU训练

yolov8、RTDETR无法使用多个GPU训练

yolov8、RTDETR无法使用多个GPU训练 网上看了好多解决方法&#xff1a; 什么命令行 CUDA_VISIBLE_DEVICES0,1 python train.py 环境变量都不行 最后找到解决方案&#xff1a;在ultralytics/engine/trainer.py 中的第246行 将 self.model DDP(self.model, device_ids[RANK])…
阅读更多...
学习测试7-ADB的使用

学习测试7-ADB的使用

ADB是什么&#xff1f; ADB&#xff0c;即 Android Debug Bridge&#xff08;安卓调试桥&#xff09; 是一种允许模拟器或已连接的 Android 设备进行通信的命令行工具&#xff0c;它可为各种设备操作提供便利&#xff0c;如安装和调试应用&#xff0c;并提供对 Unix shell&…
阅读更多...
C++|智能指针

C++|智能指针

目录 引入 一、智能指针的使用及原理 1.1RAII 1.2智能指针原理 1.3智能指针发展 1.3.1std::auto_ptr 1.3.2std::unique_ptr 1.3.3std::shared_ptr 二、循环引用问题及解决方法 2.1循环引用 2.2解决方法 三、删除器 四、C11和boost中智能指针的关系 引入 回顾上…
阅读更多...
如何分析软件测试中发现的Bug！

如何分析软件测试中发现的Bug！

假如你是一名软件测试工程师&#xff0c;每天面对的就是那些“刁钻”的Bug&#xff0c;它们像是隐藏在黑暗中的敌人&#xff0c;时不时跳出来给你一个“惊喜”。那么&#xff0c;如何才能有效地分析和处理这些Bug&#xff0c;让你的测试工作变得高效且有趣呢&#xff1f;今天我…
阅读更多...
SpringBoot配置flyway

SpringBoot配置flyway

背景 目前我们的项目代码都会交由Git、SVN等版本管理工具进行管理&#xff0c;但是我们的sql脚本&#xff0c;尤其是各类ddl脚本并没有进行版本的管理&#xff08;python的web框架Django默认就提供了类似的工具&#xff0c;从一开始就鼓励开发者通过版本管理的方式进行数据库的…
阅读更多...
Android Studio 的Gradle下载慢，Gradle切换下载源

Android Studio 的Gradle下载慢，Gradle切换下载源

看图 下面的文字地址因为转义符号的问题&#xff0c;https后面少了一个斜杠看图片进行补充&#xff0c;直接复制不知道能不能用 distributionUrlhttps://mirrors.cloud.tencent.com/gradle/gradle-8.7-bin.zip
阅读更多...
第一关：Linux基础知识

第一关：Linux基础知识

Linux基础知识目录 前言LinuxInternStudio 关卡1. InternStudio开发机介绍2. SSH及端口映射2.1 什么是SSH&#xff1f;2.2 如何使用SSH远程连接开发机&#xff1f;2.2.1 使用密码进行SSH远程连接2.2.2 配置SSH密钥进行SSH远程连接2.2.3 使用VScode进行SSH远程连接 2.3. 端口映射…
阅读更多...
进度条提示-在python程序中使用避免我误以为挂掉了

进度条提示-在python程序中使用避免我误以为挂掉了

使用库tqdm 你还可以手写一点&#xff0c;反正只要是输出点什么东西都可以&#xff1b; Demo from chatgpt import time from tqdm import tqdm# 示例函数&#xff0c;模拟长时间运行的任务 def long_running_task():total_steps 100for step in tqdm(range(total_steps), …
阅读更多...
手机容器化 安装docker

手机容器化 安装docker

旧手机-基于Termux容器化 1、安装app 在手机上安装Termux或ZeroTermux&#xff08;Termux扩展&#xff09; 1.1 切换源 注&#xff1a;可以将termux进行换源&#xff0c;最好采用国内源&#xff0c;例如&#xff1a;清华源等 更新包列表和升级包&#xff08;可选&#xff0…
阅读更多...
vue 画二维码及长按保存

vue 画二维码及长按保存

需求 想要做如下图的二维码带文字&#xff0c;且能够长按保存 前期准备 一个canvas安装qrcode&#xff08;命令&#xff1a;npm i qrcode&#xff09; 画二维码及文字 初始化画布 <template><div><canvas ref"canvas" width"300" he…
阅读更多...
8627 数独

8627 数独

为了判断数独解是否合法&#xff0c;我们需要遵循以下步骤&#xff1a; 1. **检查每一行**&#xff1a;确保1到9每个数字在每一行中只出现一次。 2. **检查每一列**&#xff1a;确保1到9每个数字在每一列中只出现一次。 3. **检查每个3x3的宫**&#xff1a;确保1到9每个数字在…
阅读更多...
在pycharm中使用jupyter

在pycharm中使用jupyter

在pycharm中使用jupyter 前置条件&#xff1a;你的环境中应该有juptyer &#xff0c;没有的话 pip install jupyter 点击项目目录&#xff0c;右键->new->jupyter notebook 打开file settings 找到 jupyter server &#xff08;按照默认的用代理服务器就行&#xff09; P…
阅读更多...
东芝 TB5128FTG 强大性能的步进电机驱动器

东芝 TB5128FTG 强大性能的步进电机驱动器

TB5128FTG它以高精度和高效能为设计理念&#xff0c;采用 PWM 斩波方法&#xff0c;并内置时钟解码器。通过先进的 BiCD 工艺制造&#xff0c;这款驱动器提供高达 50V 和 5.0A 的输出额定值&#xff0c;成为广泛应用场景中的强劲解决方案。 主要特性 TB5128FTG 拥有众多确保高…
阅读更多...
码云远程仓库, 回滚到指定版本号

码云远程仓库, 回滚到指定版本号

1. 打开项目路径, 右击Git Bash Here 2. 查找历史版本 git reflog 3. 回退到指定版本 git reset --hard 版本号 4. 强制推送到远程 git push -f
阅读更多...
SQL基础-DQL 小结

SQL基础-DQL 小结

SQL基础-DQL 小结 学习目标&#xff1a;学习内容&#xff1a;SELECTFROMWHEREGROUP BYHAVINGORDER BY运算符ASC 和 DESC 总结 学习目标&#xff1a; 1.理解DQL&#xff08;Data Query Language&#xff09;的基本概念和作用。 2.掌握SQL查询的基本语法结构&#xff0c;包括SEL…
阅读更多...
基于Android平台开发，购物商城

基于Android平台开发，购物商城

相关视频教程在某站上面(&#x1f50d;浩宇软件开发) 1. 项目功能思维导图 2. 项目涉及到的技术点 使用SQLite数据库实现数据存储使用CountDownTimer实现启动页倒计时使用SharedPreferences实现记住密码登录使用BottomNavigationView实现底部导航栏使用ActivityFragment实现底…
阅读更多...
C++:红黑树

C++:红黑树

概念 红黑树是一种二叉搜索树&#xff0c;一般的二叉搜索会发生不平衡现象&#xff0c;导致搜索效率下降&#xff0c;于是学者们开始探索如何让二叉搜索树保持平衡&#xff0c;这种树叫做自平衡二叉搜索树。起初学者发明了AVL树&#xff0c;其通过一定算法保持了二叉搜索树的严…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023