Java 详解分析链表的中间节点
时间:2022-04-09 14:53:35|栏目:JAVA代码|点击: 次
1.题目描述
给定一个头结点为 head 的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。

题目来源:力扣(LeetCode)
2.解法
定义一个快指针 fast 和一个慢指针 slow ;fast 走两步, slow 走一步,当 fas t走到尽头时,
slow 就刚好在中间节点。因为 fast 比slow 多走一半路程

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

3.复杂度
复杂度分析
时间复杂度:O(N),其中 N 是给定链表的结点数目。
空间复杂度:O(1),只需要常数空间存放 slow 和 fast 两个指针
上一篇:Spring main方法中如何调用Dao层和Service层的方法
栏 目:JAVA代码
本文标题:Java 详解分析链表的中间节点
本文地址:http://www.codeinn.net/misctech/198642.html


阅读排行
- 1Java Swing组件BoxLayout布局用法示例
- 2java中-jar 与nohup的对比
- 3Java邮件发送程序(可以同时发给多个地址、可以带附件)
- 4Caused by: java.lang.ClassNotFoundException: org.objectweb.asm.Type异常
- 5Java中自定义异常详解及实例代码
- 6深入理解Java中的克隆
- 7java读取excel文件的两种方法
- 8解析SpringSecurity+JWT认证流程实现
- 9spring boot里增加表单验证hibernate-validator并在freemarker模板里显示错误信息(推荐)
- 10深入解析java虚拟机




