建站
咨詢
售后
建站咨詢
新聞中心
前言
創(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ù)?，F(xiàn)在，服務(wù)的1000+客戶與我們一路同行，見證我們的成長；未來，我們一起分享成功的喜悅。
沒錯，今天又是算法，馬上放假啦，心已經(jīng)飛走了。
今天繼續(xù)說說鏈表算法題：求鏈表的中間結(jié)點。
- 單鏈表反轉(zhuǎn)
- 兩個有序的鏈表合并
- 刪除鏈表倒數(shù)第n個結(jié)點
- 求鏈表的中間結(jié)點
- 鏈表中環(huán)的檢測
題目：求鏈表的中間結(jié)點
給定一個頭結(jié)點為 head 的非空單鏈表，返回鏈表的中間結(jié)點。
如果有兩個中間結(jié)點，則返回第二個中間結(jié)點。
示例 1：輸入：[1,2,3,4,5] 輸出：此列表中的結(jié)點 3
(序列化形式：[3,4,5]) 返回的結(jié)點值為 3 。
(測評系統(tǒng)對該結(jié)點序列化表述是 [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] 輸出：此列表中的結(jié)點 4
(序列化形式：[4,5,6])
由于該列表有兩個中間結(jié)點，值分別為 3 和 4，我們返回第二個結(jié)點。
解法一
題目意思還是比較簡單的，就是找到中間結(jié)點。
首先想到的就是先算出來鏈表總長度，然后再遍歷到中間結(jié)點就可以了：
- 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;
- }
時間復(fù)雜度
一共遍歷了1次加半次。去除常量，時間復(fù)雜度為O(n)
空間復(fù)雜度
只用到單獨的一個鏈表結(jié)點，空間復(fù)雜度為O(1)
解法二
還記得上一篇我們說到的找到結(jié)尾第n個結(jié)點算法題嗎?其中用到了一個叫做快慢指針的解法。
在這里依然可以用到?？赡苣憔陀幸苫罅?，上一次是知道兩個指針之間相隔n個結(jié)點，這一次怎么用呢?
如果我們將慢指針每次移動一格，快指針每次移動兩格，那么快指針是不是每次都是慢指針的兩倍步數(shù)呢?
這樣當(dāng)快指針移到尾部的時候，慢指針就剛好在中間結(jié)點了。
- 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都要移動兩步，所以需要判斷當(dāng)前結(jié)點和下一個結(jié)點是否都為空。
- slow 1 2 3 4 5 6
- fast 1 3 5 7 9 11
上面的例子就是快慢指針會走到的節(jié)點數(shù)：
- 如果鏈表為奇數(shù)，比如[1,2,3,4,5]，那么剛好快慢結(jié)點就會走到3和5。
- 如果鏈表為奇數(shù)，比如[1,2,3,4,5,6]，那么剛好快慢結(jié)點就會走到4和null。
時間復(fù)雜度
用到了遍歷，所以時間復(fù)雜度還是O(n)
空間復(fù)雜度
空間復(fù)雜度為O(1)
其他解法
如果該題是數(shù)組的話，是不是一句代碼就能解出來呢?Array[n/2]。所以我們完全可以將鏈表轉(zhuǎn)化成數(shù)組，然后一句代碼就可以輸出中間結(jié)點數(shù)了，你可以動手試試哦。
這種解法的時間復(fù)雜度和空間復(fù)雜度又是多少呢?
參考
https://leetcode-cn.com/problems/middle-of-the-linked-list/
本文轉(zhuǎn)載自微信公眾號「碼上積木」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系碼上積木公眾號。
新聞標(biāo)題：LeetCode題解之求鏈表的中間結(jié)點
轉(zhuǎn)載來于：http://www.dlmjj.cn/article/cddccgo.html
