链表中点查找的四种情况

chatgpt/2023/9/26 13:34:02

在处理链表问题时,常常会遇到需要找到链表中点的情况。这里我们讨论四种常见的情况,并提供了相应的Java代码实现。

1. 寻找链表的中点或上中点

在链表节点数量为奇数时,中点只有一个;为偶数时,我们定义第 N/2 个节点为上中点。

public static Node midOrUpMidNode(Node head) {if (head == null || head.next == null || head.next.next == null) {return head;}Node slow = head.next;Node fast = head.next.next;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow;
}

2. 寻找链表的中点或下中点

在链表节点数量为偶数时,我们定义第 N/2 + 1 个节点为下中点。
public static Node midOrDownMidNode(Node head) {

 if (head == null || head.next == null) {return head;}Node slow = head.next;Node fast = head.next;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow;
}

3. 寻找链表的中点或上中点的前一个节点

public static Node midOrUpMidPreNode(Node head) {if (head == null || head.next == null || head.next.next == null) {return null;}Node slow = head;Node fast = head.next.next;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow;
}

4. 寻找链表的中点或下中点的前一个节点

public static Node midOrDownMidPreNode(Node head) {if (head == null || head.next == null) {return null;}if (head.next.next == null) {return head;}Node slow = head;Node fast = head.next;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow;
}

以上四种方法的核心思想都是利用快慢指针。快指针每次走两步,慢指针每次走一步。当快指针走到链表尾部时,慢指针正好在链表的中点。在处理链表问题时,快慢指针是一个非常常用也非常有效的技巧。
以上就是链表中点查找的四种常见情况的Java实现,希望对大家有所帮助。

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

如若内容造成侵权/违法违规/事实不符,请联系郑州代理记账网进行投诉反馈,一经查实,立即删除!

相关文章

图观| 从王宝强、费翔、阿汤哥等新上映的电影聊聊图的智能推荐场景

从技术的视角来看,推荐系统本质上是在用户需求不明确的情况下,从海量的信息中为用户过滤出他可能感兴趣的信息的一种技术手段。 我们日常接触到的智能推荐有: 电商网站:如淘宝、天猫、京东、Amazon…… 生活服务:如美…

日撸java_day54-55

文章目录 第 54 、55 天: 基于 M-distance 的推荐代码运行截图 第 54 、55 天: 基于 M-distance 的推荐 1.M-distance, 就是根据平均分来计算两个用户 (或项目) 之间的距离. 2.邻居不用 k 控制. 距离小于 radius (即 ϵ ) 的都是邻居. 使用 M-distance 时, 这种方式效果更好. …

1.0 python环境安装

1 python环境安装 python安装教程原文 2 PyCharm安装教程 PyCharm安装教程

CS5213 国产HDMI转VGA带音频方案芯片|CS5213规格书|CS5213原理图

集睿致远/ASL推出的CS5213芯片是一个国产HDMI(高清多媒体接口)到VGA桥接芯片。它将HDMI信号转换为标准VGA信号它可以在适配器、智能电缆等设备中设计 CS5213特征 将HDMI信号转换为VGA输出 支持数字信号到模似信号的转换 支持 HDCP 1.0/1.1/1.2 操作简…

71. ElasticSearch 5.0.0 安装部署常见错误或问题

文章目录 ElasticSearch 5.0.0 安装部署常见错误或问题问题一:UnsupportedOperationException问题二:ERROR: bootstrap checks failed问题三:max number of threads [1024] for user [es] likely too low, increase to at least [2048]问题四…

史上最全免费在线 PDF 格式转换网站集合,10款利器赶紧收藏

hi,大家好我是技术苟,每天晚上22点准时上线为你带来实用黑科技!由于公众号改版,现在的公众号消息已经不再按照时间顺序排送了。因此小伙伴们就很容易错过精彩内容。喜欢黑科技的小伙伴,可以将黑科技百科公众号设为标星…

day53|● 1143.最长公共子序列 ● 1035.不相交的线 ● 53. 最大子序和

最长重复子数组 Input: nums1 [1,2,3,2,1], nums2 [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3,2,1]. dp[i][j] :以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。 …

达梦数据库食用说明

环境准备 达梦数据库支持Windows、Linux和Unix操作系统,达梦正式版需要授权,我们学习的话选择试用即可,在本机使用VM安装一个Centos,然后去达梦官网下载适用自己平台的安装包。 本教程使用的是VM安装的centos7.9。所以选择X86架…
推荐文章