195、連結清單的中間結點

題目描述：

給定一個帶有頭結點 head 的非空單連結清單，傳回連結清單的中間結點。

如果有兩個中間結點，則傳回第二個中間結點。

示例 1：

輸入：[1,2,3,4,5]

輸出：此清單中的結點 3 (序列化形式：[3,4,5])

傳回的結點值為 3 。 (測評系統對該結點序列化表述是 [3,4,5])。

注意，我們傳回了一個 ListNode 類型的對象 ans，這樣：

ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

輸入：[1,2,3,4,5,6]

輸出：此清單中的結點 4 (序列化形式：[4,5,6])

由于該清單有兩個中間結點，值分别為 3 和 4，我們傳回第二個結點。

提示：

給定連結清單的結點數介于 1 和 100 之間。

在真實的面試中遇到過這道題？

設定兩個指針，一個是以兩倍的速度前進，一個是以一倍速度前進，然後判斷兩倍速度是否到達終點，此時就傳回

代碼如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
      if(head == null){
			return head;
		}
		if(head.next == null){
			return head;
		}
		if(head.next.next == null){
			return head.next;
		}
		
		
		ListNode pre = head;
		ListNode last = head;
		
		while (pre != null && last != null && pre.next != null && last.next != null) {
			pre = pre.next;
			last = last.next.next;
		}
		
		return pre;  
    }
}