LintCode:链表的中点

描述

找链表的中点。

样例

样例 1:

输入: 1->2->3
输出: 2
样例解释: 返回中间节点的值

样例 2:

输入: 1->2
输出: 1
样例解释: 如果长度是偶数，则返回中间偏左的节点的值。

挑战

如果链表是一个数据流，你可以不重新遍历链表的情况下得到中点么？
思路：快慢指针法。
这里使用快慢指针寻找中点
可以保证时间复杂度为O(n/2)
快指针每次走两步，慢指针每次走一步，快指针到尾部的时候，慢指针的位置就是一半

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

    public static ListNode middleNode(ListNode head) {
        ListNode quickCur = head;
        ListNode slowCur = head;
        if (head == null || head.next == null) {
            return head;
        }
        while (quickCur.next != null && quickCur.next.next != null) {
            quickCur = quickCur.next.next;
            slowCur = slowCur.next;
        }
        return slowCur;
    }