建站
咨詢
售后
建站咨詢
新聞中心
前言
創(chuàng)新互聯(lián)是一家專注網(wǎng)站建設(shè)、網(wǎng)絡(luò)營銷策劃、微信小程序定制開發(fā)、電子商務(wù)建設(shè)、網(wǎng)絡(luò)推廣、移動互聯(lián)開發(fā)、研究、服務(wù)為一體的技術(shù)型公司。公司成立十余年以來，已經(jīng)為1000+汽車玻璃修復(fù)各業(yè)的企業(yè)公司提供互聯(lián)網(wǎng)服務(wù)。現(xiàn)在，服務(wù)的1000+客戶與我們一路同行，見證我們的成長；未來，我們一起分享成功的喜悅。
沒錯(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 。
(測評系統(tǒng)對該結(jié)點(diǎn)序列化表述是 [3,4,5])。注意，我們返回了一個(gè) 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é)點(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)，這一次怎么用呢?
如果我們將慢指針每次移動一格，快指針每次移動兩格，那么快指針是不是每次都是慢指針的兩倍步數(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)前結(jié)點(diǎn)和下一個(gè)結(jié)點(diǎn)是否都為空。
- slow 1 2 3 4 5 6
- fast 1 3 5 7 9 11
上面的例子就是快慢指針會走到的節(jié)點(diǎn)數(shù)：
- 如果鏈表為奇數(shù)，比如[1,2,3,4,5]，那么剛好快慢結(jié)點(diǎn)就會走到3和5。
- 如果鏈表為奇數(shù)，比如[1,2,3,4,5,6]，那么剛好快慢結(jié)點(diǎn)就會走到4和null。
時(shí)間復(fù)雜度
用到了遍歷，所以時(shí)間復(fù)雜度還是O(n)
空間復(fù)雜度
空間復(fù)雜度為O(1)
其他解法
如果該題是數(shù)組的話，是不是一句代碼就能解出來呢?Array[n/2]。所以我們完全可以將鏈表轉(zhuǎn)化成數(shù)組，然后一句代碼就可以輸出中間結(jié)點(diǎn)數(shù)了，你可以動手試試哦。
這種解法的時(shí)間復(fù)雜度和空間復(fù)雜度又是多少呢?
參考
https://leetcode-cn.com/problems/middle-of-the-linked-list/
本文轉(zhuǎn)載自微信公眾號「碼上積木」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系碼上積木公眾號。
網(wǎng)頁名稱：LeetCode題解之求鏈表的中間結(jié)點(diǎn)
鏈接URL：http://fisionsoft.com.cn/article/cddccgo.html
