校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 单向链表
题目

找出单链表的中间元素,要求用时最少

解答

正常的话,需要先遍历一圈,得到链表长度。再从头遍历到1/2长度的位置。

也就是走了1.5倍的链表长度


这是个题型,使用两个指针slow, fast , 一个一次走一步,一个走两步。当fast到达结尾时,slow就在中间。

Node findMiddle(Node head)
{
            If(head == null || head.next == null){
                        return head;//偶数返回中间靠前结点
            }
            Node slow  = head;  
            Node fast = head;
            while( fast.next != null  && fast.next.next != null )  {  
                      fast = fast.next.next;  
                      slow = slow.next;  
            }  
           return slow;
}



C 5条回复 评论
六元的大可爱er

请教一下懒汉式单例的第三种线程安全改造与饿汉式还有什么区别??

发表于 2021-12-06 14:40:00
0 0
dana

面试常考的偏简单的那一类题,就是不能出错

发表于 2018-11-21 17:56:36
0 0
dana

这是一种题型,当然也可以考虑求第K个位置的结点

发表于 2019-03-26 14:13:50
0 1
dana

顶上去,。。

发表于 2019-03-26 14:14:01
0 1
繁星知晓

两个指针只用一半的时间,这个思路很好啊

发表于 2018-10-13 14:31:41
0 0