題目
難度：★☆☆☆☆
類型：鏈表
給定一個(gè)帶有頭結(jié)點(diǎn) head 的非空單鏈表新翎，返回鏈表的中間結(jié)點(diǎn)惠赫。
如果有兩個(gè)中間結(jié)點(diǎn)终蒂，則返回第二個(gè)中間結(jié)點(diǎn)席里。
提示
給定鏈表的結(jié)點(diǎn)數(shù)介于 1 和 100 之間。
示例
示例 1
輸入：[1,2,3,4,5]
輸出：此列表中的結(jié)點(diǎn) 3 (序列化形式：[3,4,5])
返回的結(jié)點(diǎn)值為 3 供汛。 (測評(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)趁舀。
解答
方案1：統(tǒng)計(jì)長度
我們可以統(tǒng)計(jì)鏈表的長度赖捌，然后再次遍歷，將一半長度處的結(jié)點(diǎn)取出矮烹。
class Solution:
def middleNode(self, head):
"""
:param head: ListNode
:return: ListNode
"""
def get_len(node):
tmp = node
count = 0
while tmp:
count += 1
tmp = tmp.next
return count
def get_node(node, idx):
tmp = node
count = 0
while count < idx:
count += 1
tmp = tmp.next
return tmp
return get_node(head, get_len(head)//2)
方案2：快慢指針
定義快慢指針越庇，同時(shí)從頭結(jié)點(diǎn)開始向后遍歷，快指針每次走兩步奉狈，慢指針每次走一步卤唉，當(dāng)快指針走到末尾結(jié)點(diǎn)時(shí)，慢指針恰好走到中間結(jié)點(diǎn)仁期。
class Solution:
def middleNode(self, head):
"""
:param head: ListNode
:return: ListNode
"""
fast = slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
如有疑問或建議桑驱，歡迎評(píng)論區(qū)留言~
