LeetCode題解之求鏈表的中間結點
前言
沒錯，今天又是算法，馬上放假啦，心已經飛走了。
今天繼續說說鏈表算法題：求鏈表的中間結點。
- 單鏈表反轉
- 兩個有序的鏈表合并
- 刪除鏈表倒數第n個結點
- 求鏈表的中間結點
- 鏈表中環的檢測
題目：求鏈表的中間結點
給定一個頭結點為 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。
時間復雜度
用到了遍歷，所以時間復雜度還是O(n)
空間復雜度
空間復雜度為O(1)
其他解法
如果該題是數組的話，是不是一句代碼就能解出來呢?Array[n/2]。所以我們完全可以將鏈表轉化成數組，然后一句代碼就可以輸出中間結點數了，你可以動手試試哦。
這種解法的時間復雜度和空間復雜度又是多少呢?
參考
https://leetcode-cn.com/problems/middle-of-the-linked-list/
本文轉載自微信公眾號「碼上積木」，可以通過以下二維碼關注。轉載本文請聯系碼上積木公眾號。
