链表的中间结点

链表的中间结点

思路1：
1.若链表为空，直接返回null
2.若链表不为空，我们可以先求的链表的长度，让得到的链表长度/2，再让ListNode cur=head，cur走上链表长度/2次，就可以返回中间节点了

    public int size(ListNode head){
        if(head==null){
            return 0;
        }
        ListNode cur=head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    public ListNode middleNode(ListNode head) {
         int count=size(head)/2;
        ListNode cur=head;
        while(count!=0){
            cur=cur.next;
            count--;
        }
        return cur;
    }
 } 

由于思路1遍历了两次链表，我们只希望遍历一次就可以找到中间结点

思路2：

1.若链表为空，直接返回null
2.若链表不为空， 我们定义两个指向节点的对象分别是fast和slow fast每次走两步，slow每次走一步 根据路程公式s=vt，fast的速度是slow的两倍，当fast走到终点时，slow此时所指向的节点就是中间节点
此时会有一个问题就是链表的长度为偶数和奇数的两种情况：

    public ListNode middleNode(ListNode head) {
         if(head==null){
            return head;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    } 
}