本篇內(nèi)容介紹了“LeetCode題解之怎么求鏈表的中間結(jié)點”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

創(chuàng)新互聯(lián)專注于新城企業(yè)網(wǎng)站建設(shè),成都響應(yīng)式網(wǎng)站建設(shè)公司,商城開發(fā)。新城網(wǎng)站建設(shè)公司,為新城等地區(qū)提供建站服務(wù)。全流程按需求定制設(shè)計，專業(yè)設(shè)計，全程項目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)

題目：求鏈表的中間結(jié)點

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

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

示例 1：輸入：[1,2,3,4,5] 輸出：此列表中的結(jié)點 3

(序列化形式：[3,4,5]) 返回的結(jié)點值為 3 。

(測評系統(tǒng)對該結(jié)點序列化表述是 [3,4,5])。注意，我們返回了一個 ListNode 類型的對象 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é)點 4

(序列化形式：[4,5,6])

由于該列表有兩個中間結(jié)點，值分別為 3 和 4，我們返回第二個結(jié)點。

解法一

題目意思還是比較簡單的，就是找到中間結(jié)點。

首先想到的就是先算出來鏈表總長度，然后再遍歷到中間結(jié)點就可以了：

public ListNode middleNode(ListNode head) {         int n = 0;         ListNode cur = head;         while (cur != null) {             n++;             cur = cur.next;         }         int k = 0;         cur = head;         while (k < n / 2) {             k++;             cur = cur.next;         }         return cur;     }

時間復(fù)雜度

一共遍歷了1次加半次。去除常量，時間復(fù)雜度為O(n)

空間復(fù)雜度

只用到單獨的一個鏈表結(jié)點，空間復(fù)雜度為O(1)

解法二

還記得上一篇我們說到的找到結(jié)尾第n個結(jié)點算法題嗎?其中用到了一個叫做快慢指針的解法。

在這里依然可以用到?？赡苣憔陀幸苫罅?，上一次是知道兩個指針之間相隔n個結(jié)點，這一次怎么用呢?

如果我們將慢指針每次移動一格，快指針每次移動兩格，那么快指針是不是每次都是慢指針的兩倍步數(shù)呢?

這樣當(dāng)快指針移到尾部的時候，慢指針就剛好在中間結(jié)點了。

public ListNode middleNode(ListNode head) {         ListNode slow = head;         ListNode fast = head;         while (fast != null && fast.next != null) {             slow = slow.next;             fast = fast.next.next;         }         return slow;     }

這里因為每次fast都要移動兩步，所以需要判斷當(dāng)前結(jié)點和下一個結(jié)點是否都為空。

slow 1  2  3  4  5  6   fast 1  3  5  7  9  11

上面的例子就是快慢指針會走到的節(jié)點數(shù)：

• 如果鏈表為奇數(shù)，比如[1,2,3,4,5]，那么剛好快慢結(jié)點就會走到3和5。

• 如果鏈表為奇數(shù)，比如[1,2,3,4,5,6]，那么剛好快慢結(jié)點就會走到4和null。

“LeetCode題解之怎么求鏈表的中間結(jié)點”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！

標(biāo)題名稱：LeetCode題解之怎么求鏈表的中間結(jié)點
網(wǎng)站URL：http://aaarwkj.com/article46/gpichg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開發(fā)、網(wǎng)站改版、微信公眾號、響應(yīng)式網(wǎng)站、用戶體驗、靜態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)