数据结构-链表-单向链表
面5笔5找出单链表的中间元素,要求用时最少
正常的话,需要先遍历一圈,得到链表长度。再从头遍历到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;
}