leetCode第876題 鏈表的中間結(jié)點(diǎn)
鏈接：https://leetcode-cn.com/problems/middle-of-the-linked-list

給定一個(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 類(lèi)型的對(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 之間。

一般的方法當(dāng)然是先算出鏈表的長(zhǎng)度，然后計(jì)算中間結(jié)點(diǎn)的位置，然后將這個(gè)結(jié)點(diǎn)返回。
這樣計(jì)算長(zhǎng)度循環(huán)一次，尋找結(jié)點(diǎn)循環(huán)一次，時(shí)間復(fù)雜度也在O(n)級(jí)別。
但設(shè)立快慢指針能使循環(huán)減小到一次。
快慢指針都設(shè)置在head處，fast步長(zhǎng)為2，slow步長(zhǎng)為1，因?yàn)閒ast速度是slow的兩倍，所以當(dāng)fast到了鏈表末尾，slow剛好在鏈表中間。

## python3 class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next class Solution:def middleNode(self, head: ListNode) -> ListNode:slow = headfast = headwhile fast != None and fast.next != None:slow = slow.nextfast = fast.next.nextreturn slow

總結(jié)

以上是生活随笔為你收集整理的链表的中间结点-python的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。