建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
前言
創(chuàng)新互聯(lián)是一家專(zhuān)注網(wǎng)站建設(shè)、網(wǎng)絡(luò)營(yíng)銷(xiāo)策劃、微信小程序定制開(kāi)發(fā)、電子商務(wù)建設(shè)、網(wǎng)絡(luò)推廣、移動(dòng)互聯(lián)開(kāi)發(fā)、研究、服務(wù)為一體的技術(shù)型公司。公司成立十余年以來(lái)，已經(jīng)為1000+汽車(chē)玻璃修復(fù)各業(yè)的企業(yè)公司提供互聯(lián)網(wǎng)服務(wù)?，F(xiàn)在，服務(wù)的1000+客戶(hù)與我們一路同行，見(jiàn)證我們的成長(zhǎng)；未來(lái)，我們一起分享成功的喜悅。
沒(méi)錯(cuò)，今天又是算法，馬上放假啦，心已經(jīng)飛走了。
今天繼續(xù)說(shuō)說(shuō)鏈表算法題：求鏈表的中間結(jié)點(diǎn)。
- 單鏈表反轉(zhuǎn)
- 兩個(gè)有序的鏈表合并
- 刪除鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)
- 求鏈表的中間結(jié)點(diǎn)
- 鏈表中環(huán)的檢測(cè)
題目：求鏈表的中間結(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 。
(測(cè)評(píng)系統(tǒng)對(duì)該結(jié)點(diǎn)序列化表述是 [3,4,5])。注意，我們返回了一個(gè) ListNode 類(lèi)型的對(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ǎn)單的，就是找到中間結(jié)點(diǎn)。
首先想到的就是先算出來(lái)鏈表總長(zhǎng)度，然后再遍歷到中間結(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)
解法二
還記得上一篇我們說(shuō)到的找到結(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ù)組的話，是不是一句代碼就能解出來(lái)呢?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ò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系碼上積木公眾號(hào)。
文章標(biāo)題：LeetCode題解之求鏈表的中間結(jié)點(diǎn)
本文URL：http://m.5511xx.com/article/cddccgo.html
