天天看點

【leetcode】876. Middle of the Linked List

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:

【leetcode】876. Middle of the Linked List

Example 2:

【leetcode】876. Middle of the Linked List

    本題的需求是傳回一個連結清單的中間節點,屬于那種一眼就能想到如何解答的easy題目。

    解法一,利用map存儲每個節點以及節點的位置,然會中間位置的節點。

     解法二,上述解法空間複雜度太高,其實還可以用快慢指針解決,快指針每個循環走兩步,慢指針每個循環走一步,當快指針結束的時候,慢指針剛好走到了一半,即中間位置。(如下圖所示 龜兔賽跑)

【leetcode】876. Middle of the Linked List