欢迎来到代码驿站!

JAVA代码

当前位置:首页 > 软件编程 > JAVA代码

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代码

下一篇:MyBatis insert实体如何返回主键

本文标题:Java 详解分析链表的中间节点

本文地址:http://www.codeinn.net/misctech/198642.html

推荐教程

广告投放 | 联系我们 | 版权申明

重要申明:本站所有的文章、图片、评论等,均由网友发表或上传并维护或收集自网络,属个人行为,与本站立场无关。

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ:914707363 | 邮箱:codeinn#126.com(#换成@)

Copyright © 2020 代码驿站 版权所有