Middle of Linked List

Description

Find the middle node of a linked list.

Example

Given 1->2->3, return the node with value 2.

Given 1->2, return the node with value 1.

Challenge

If the linked list is in a data stream, can you find the middle without iterating the linked list again?

/** * Definition for ListNode * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    /**     * @param head: the head of linked list.     * @return: a middle node of the linked list     */    public ListNode middleNode(ListNode head) {        // write your code here        if(head==null) return null;        ListNode slow=head;        ListNode fast=head;        while(fast.next!=null&&fast.next.next!=null){            slow=slow.next;            fast=fast.next.next;        }        return slow;    }}

描述找链表的中点。您在真实的面试中是否遇到过这个题？  样例链表 1->2->3 的中点是 2。链表 1->2 的中点是 1。挑战如果链表是一个数据流，你可以不重新遍历链表的情况下得到中点么？