原题链接在这里：

题目：

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]Output: Node 3 from this list (Serialization: [3,4,5])The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).Note that we returned a ListNode object ans, such that:ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]Output: Node 4 from this list (Serialization: [4,5,6])Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

• The number of nodes in the given list will be between 1 and 100.

题解：

walker每次跳一步. runner每次跳两步. runner 跳到尾时, walker就是中点.

list偶数长度时, 中点找中间两个前者时, while的终止条件到是(runner != null && runner.next != null && runner.next.next != null).

找后者时, while的终止条件是(runner != null && runner.next != null).

Time Complexity: O(n).

Space: O(1).

AC Java:

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 class Solution {10     public ListNode middleNode(ListNode head) {11         if(head == null || head.next == null){12             return head;13         }14         15         ListNode walker = head;16         ListNode runner = head;17         while(runner != null && runner.next != null){18             walker = walker.next;19             runner = runner.next.next;20         }21         22         return walker;23     }24 }