leetCode-链表的中间结点

题目描述：给定一个头结点为 head 的非空单链表，返回链表的中间结点
如果有两个中间结点，则返回第二个中间结点。

思路:

• 方法一：java快慢指针

class Solution {
    public ListNode middleNode(ListNode head) {
          ListNode p = head, q = head;
        while (q != null && q.next != null) {
            q = q.next.next;
            p = p.next;
        }
        return p;
}
}

• 方法二：单指针法

class Solution {
   public ListNode middleNode(ListNode head) {
       int n = 0;
       ListNode cur = head;
       while (cur != null) {
           ++n;
           cur = cur.next;
       }
       int k = 0;
       cur = head;
       while (k < n / 2) {
           ++k;
           cur = cur.next;
       }
       return cur;
   }
}