一、題目描述

給定一個(gè)頭結(jié)點(diǎn)為head的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。

如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)中間結(jié)點(diǎn)。

示例 1：

輸入：[1,2,3,4,5]
輸出：此列表中的結(jié)點(diǎn) 3 (序列化形式：[3,4,5])
返回的結(jié)點(diǎn)值為 3 。(測(cè)評(píng)系統(tǒng)對(duì)該結(jié)點(diǎn)序列化表述是[3,4,5])。
注意，我們返回了一個(gè) ListNode 類型的對(duì)象 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]
輸出：此列表中的結(jié)點(diǎn) 4 (序列化形式：[4,5,6])
由于該列表有兩個(gè)中間結(jié)點(diǎn)，值分別為 3 和 4，我們返回第二個(gè)結(jié)點(diǎn)。

提示：

給定鏈表的結(jié)點(diǎn)數(shù)介于1和100之間。

二、題目解析

我個(gè)人認(rèn)為這道題目是最好理解快慢指針這個(gè)知識(shí)點(diǎn)了。

不難理解整體的思路如下：

1、設(shè)置兩個(gè)指針，一開始都指向鏈表的頭節(jié)點(diǎn)；

2、接下來，讓這兩個(gè)指針向前移動(dòng)；

3、如果可以移動(dòng)，那么就會(huì)讓快指針每次移動(dòng)兩步，慢指針每次移動(dòng)一步；

4、而快指針可以移動(dòng)兩步的前提就是當(dāng)前節(jié)點(diǎn)不為空，同時(shí)下一節(jié)點(diǎn)也不為空，這樣才能保證 fast.next 有值、fast.next.next 有值

5、最后，slow 指向的就是中間節(jié)點(diǎn)。

三、參考代碼

// LeetCode 100題精講：https://mp.weixin.qq.com/s/yznC53g46phq3qF7V4-obA
//作者：程序員吳師兄
//鏈表的中間結(jié)點(diǎn)（LeetCode 876）：https://leetcode.cn/problems/middle-of-the-linked-list/
classSolution{
publicListNodemiddleNode(ListNodehead){

//設(shè)置兩個(gè)指針，一開始都指向鏈表的頭節(jié)點(diǎn)
ListNodeslow=head;

ListNodefast=head;

//接下來，讓這兩個(gè)指針向前移動(dòng)
//如果可以移動(dòng)，那么就會(huì)讓快指針每次移動(dòng)兩步，慢指針每次移動(dòng)一步
//而快指針可以移動(dòng)兩步的前提就是當(dāng)前節(jié)點(diǎn)不為空，同時(shí)下一節(jié)點(diǎn)也不為空
//這樣才能保證fast.next有值、fast.next.next有值
while(fast!=null&&fast.next!=null){

//慢指針每次移動(dòng)一步
slow=slow.next;

//快指針每次移動(dòng)兩步
fast=fast.next.next;
}

//最后，slow指向的就是中間節(jié)點(diǎn)
returnslow;

}
}

審核編輯：劉清