[[380452]]

前言

沒錯(cuò)，今天又是算法，馬上放假啦，心已經(jīng)飛走了。

今天繼續(xù)說說鏈表算法題：求鏈表的中間結(jié)點(diǎn)。

• 單鏈表反轉(zhuǎn)
• 兩個(gè)有序的鏈表合并
• 刪除鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)
• 求鏈表的中間結(jié)點(diǎn)
• 鏈表中環(huán)的檢測

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

給定一個(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 。

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

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

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

時(shí)間復(fù)雜度

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

空間復(fù)雜度

只用到單獨(dú)的一個(gè)鏈表結(jié)點(diǎn)，空間復(fù)雜度為O(1)

解法二

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

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

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

這樣當(dāng)快指針移到尾部的時(shí)候，慢指針就剛好在中間結(jié)點(diǎ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; 
    } 

這里因?yàn)槊看蝔ast都要移動(dòng)兩步，所以需要判斷當(dāng)前結(jié)點(diǎn)和下一個(gè)結(jié)點(diǎn)是否都為空。

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

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

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

時(shí)間復(fù)雜度

用到了遍歷，所以時(shí)間復(fù)雜度還是O(n)

空間復(fù)雜度

空間復(fù)雜度為O(1)

其他解法

如果該題是數(shù)組的話，是不是一句代碼就能解出來呢?Array[n/2]。所以我們完全可以將鏈表轉(zhuǎn)化成數(shù)組，然后一句代碼就可以輸出中間結(jié)點(diǎn)數(shù)了，你可以動(dòng)手試試哦。

這種解法的時(shí)間復(fù)雜度和空間復(fù)雜度又是多少呢?

參考

https://leetcode-cn.com/problems/middle-of-the-linked-list/

本文轉(zhuǎn)載自微信公眾號(hào)「碼上積木」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系碼上積木公眾號(hào)。