我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 876. 鏈表的中間結點

題目

給定一個帶有頭結點 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 之間。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/middle-of-the-linked-list
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

思路1-兩次遍歷，一次統計總數n，另一次直接遍歷到n/2；

思路2-一次遍歷並放入list，最後直接取即可：list.get(list.size()/2);

思路1、2都比較簡單，以下代碼略；

思路3-使用快慢指針，快指針每次移動兩個節點，慢指針每次移動一個節點，快指針移動到末尾時，慢指針的位置就是中間位置；

Tips：在定位鏈表的倒數第n節點時也可使用快慢指針

演算法源碼示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2020年3月23日 上午12:11:23 
 * @Description: 876. 鏈表的中間結點
 *
 */
public class LeetCode_0876 {

}

//  Definition for singly-linked list.
class ListNode_0876 {
	int val;
	ListNode_0876 next;

	ListNode_0876(int x) {
		val = x;
	}
}

class Solution_0876 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年3月23日 上午12:14:38 
	 * @param: @param head
	 * @param: @return
	 * @return: ListNode_0876
	 * @Description: 2-兩個指針，一個每次移動一步，另一個每次移動兩步
	 *
	 */
	public ListNode_0876 middleNode(ListNode_0876 head) {
		ListNode_0876 fast = head;
		ListNode_0876 slow = head;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
}