解答
正常的话,需要先遍历一圈,得到链表长度。再从头遍历到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;
}
请教一下懒汉式单例的第三种线程安全改造与饿汉式还有什么区别??
面试常考的偏简单的那一类题,就是不能出错
这是一种题型,当然也可以考虑求第K个位置的结点
顶上去,。。
两个指针只用一半的时间,这个思路很好啊