试题
考点

数据结构-链表-单向链表

面5笔5

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

前往“校招VIP”小程序,刷题更快
最新校招难题刷题,快来进刷题群吧
解答

正常的话,需要先遍历一圈,得到链表长度。再从头遍历到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;
}



评论

dana

2019-03-26 14:14:01

0 1

繁星知晓

2018-10-13 14:31:41

0 0

加载更多