LeetCode題解之怎么求鏈表的中間結點

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

題目：求鏈表的中間結點

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

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

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

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

(測評系統對該結點序列化表述是 [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] 輸出：此列表中的結點 4

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

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

解法一

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

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

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;     }

時間復雜度

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

空間復雜度

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

解法二

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

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

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

這樣當快指針移到尾部的時候，慢指針就剛好在中間結點了。

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都要移動兩步，所以需要判斷當前結點和下一個結點是否都為空。

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

上面的例子就是快慢指針會走到的節點數：

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

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

“LeetCode題解之怎么求鏈表的中間結點”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！