首页
/
每日頭條
/
職場
/
數據結構之鍊表操作大集合
數據結構之鍊表操作大集合
更新时间:2024-12-28 05:15:44
鍊表反轉

此題屬于中低難度的題,思路并不複雜,單其中有很多易錯點,比如空指針判斷、指針丢失等;

思路:設置三個指針pre、cur、next,初始時刻pre = null,cur = head;

開始處理,首先執行next = cur.next,防止後面cur.next修改之後指針丢失;

數據結構之鍊表操作大集合(技術連載數據結構)1

鍊表反轉

環形鍊表檢測并返回入環點

這個題目技巧性很強,一般不太容易想到;大體思路如下:

首先設置快慢指針,每一次移動,快指針移動兩步(尤其需要注意第二步判斷空指針),慢指針移動移步;然後判斷兩個指針是否指向同一位置。

如果最終快指針遇見null,則無環;如果快慢指針指向了同一位置,則有環;

如果有環的化,兩指針相遇時,快指針移動到head位置,并且變為慢指針(每次移動一步);然後兩個指針再次開始移動,直到再次相遇即為入環點。(證明略)

數據結構之鍊表操作大集合(技術連載數據結構)2

環形鍊表檢測

鍊表歸并排序

二路歸并排序:假設兩個有序數組,設置兩個指針,指向0位置,将指向比較小元素的指針對應的元素存入數組,并移動指針;直到兩個指針移動完畢;

歸并排序思路:歸并排序是建立在二路歸并排序基礎之上,将數組逐漸分解,直到僅有一個元素,然後進行二路歸并排序。(先分後合的思想)

僞代碼如下:

public int[] merge(int[] nums,int start, int end){

if(start == end){

return new int[]{nums[start]};

}

int mid = (start end) / 2;

int[] s1 = merge(nums, start,mid);

int[] s2 = merge(nums,mid 1, end);

return binMerge(s1,s2);

}

鍊表歸并排序比數組歸并排序難度有所增加,但思路是一緻的,仍然是逐步分解,直到隻有一個結點,然後再合并。

主要區别在于中點的選取,關于中點選取,這裡也有現成的思路,通過快慢指針,當快指針走到終點時,慢指針即為中點。

具體實現如下:

數據結構之鍊表操作大集合(技術連載數據結構)3

連載系列:

技術連載:開篇詞

技術連載:連載提綱設計思路

技術連載:數據結構 - 數組

技術連載:數據結構 - 數組常見面試題彙總

技術連載:數據結構 - 鍊表

,
Comments
Welcome to tft每日頭條 comments! Please keep conversations courteous and on-topic. To fosterproductive and respectful conversations, you may see comments from our Community Managers.
Sign up to post
Sort by
Show More Comments
推荐阅读
學會這三句領導會刮目相看
學會這三句領導會刮目相看
不管你在哪家公司,總會有一些好人。無論在什麼面前,他們都從不懼怕自己的脾氣。雖然他們從不得罪任何人,但因為脾氣好,他們也失去了很多好機會。發脾氣的人隻能在領導面前不斷受苦。畢竟領導可以在這樣的下屬面前為所欲為。不管領導做出什麼決定,他們都沒...
2024-12-28
亞運女孩吳怡
亞運女孩吳怡
廣州亞運十周年亞運故事系列報道廣州日報全媒體記者楊敏十年前的廣州亞運會開幕式,18歲的高中畢業生吳怡意外走紅。作為禮儀志願者,她負責引領亞奧理事會主席艾哈邁德·法赫德上台,在三位中外官員緻開幕式的時候,吳怡一直保持微笑并且長時間進入直播鏡頭...
2024-12-28
何所冬暖何所夏涼安桀席郗辰吵架
何所冬暖何所夏涼安桀席郗辰吵架
何所冬暖何所夏涼安桀席郗辰吵架?華龍網10月12日13時21分訊席郗辰叮囑露露跟緊葉蔺的工作,并且讓露露說服葉蔺接下國際大導演的戲,然而葉蔺卻表示隻想做好簡愛公寓的廣告,兩人都互不退讓,讓露露非常為難露露最終還是受席郗辰指使瞞着葉蔺幫葉蔺簽...
2024-12-28
面試自我介紹模闆
面試自我介紹模闆
面試自我介紹模闆?各位考官下午好!下面我将通過簡單的面試自我介紹讓您來了解我我是來自XX大學市場營銷專業的XXX我喜歡讀書,因為它能豐富我的知識;我喜歡跑步,因為它可以磨砺我的意志,我是一個活潑開朗、熱情、執着、有堅強意志的人,下面我們就來...
2024-12-28
面對離職的員工怎麼安排交接
面對離職的員工怎麼安排交接
本文作者:嚴小雲前段時間,國務院辦公廳印發有關“減輕義務教育階段學生作業負擔以及校外培訓負擔”(雙減政策)的文件之後,新東方、好未來、高途等在線教育龍頭企業遭受重創,股價均有不同程度的下跌,大量教育類職場人也遇到了大幅度裁員的情況。網上流傳...
2024-12-28
Copyright 2023-2024 - www.tftnews.com All Rights Reserved