Given the <code>head</code> of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
Example 1:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiInBnauEDdzlGbklWbtMGbvw1My8CX3AzLcFjMwIzLcNHZh9GbwV3Lc12bj5SZk92Y0VWZs5yc0V2czF2Lc9CX6MHc0RHaiojIsJye.jpg)
Example 2:
本題的需求是傳回一個連結清單的中間節點,屬于那種一眼就能想到如何解答的easy題目。
解法一,利用map存儲每個節點以及節點的位置,然會中間位置的節點。
解法二,上述解法空間複雜度太高,其實還可以用快慢指針解決,快指針每個循環走兩步,慢指針每個循環走一步,當快指針結束的時候,慢指針剛好走到了一半,即中間位置。(如下圖所示 龜兔賽跑)