LeetCode單鏈表(LinkList)總結(jié)

一,單鏈表的創(chuàng)建

單鏈表的創(chuàng)建一般分為分為頭插發(fā)和尾插法

  • 頭插法是每次將新的節(jié)點插入到頭部,這樣得到的鏈表順序是逆序
  • 尾插法是每次將新的節(jié)點插入到尾部,這樣得到的鏈表順序是正序的. ** 值得注意的是,采用尾插法的時候需要一個尾指針,時時刻刻指向鏈表的尾部 **
二,鏈表的操作

鏈表的插入無非是插入,刪除操作.

  • ** 在插入的刪除的時候,一定要拿到他的前驅(qū)節(jié)點 **
  • ** 為了便于鏈表的操作(例如,插入刪除),一般使用帶頭結(jié)點的鏈表**

常見的插入刪除題目如下:
兩個鏈表相加LeetCode 2. Add Two Numbers
合并兩個有序的鏈表LeetCode 21. Merge Two Sorted Lists
成對交換鏈表節(jié)點LeetCode 24. Swap Nodes in Pairs
每k個節(jié)點翻轉(zhuǎn)LeetCode 25. Reverse Nodes in k-Group
鏈表逆轉(zhuǎn)LeetCode 61. Rotate List
刪除重復(fù)元素LeetCode 82. Remove Duplicates from Sorted List II

鏈表分塊LeetCode 86. Partition List
刪除鏈表節(jié)點LeetCode 203. Remove Linked List Elements

三,鏈表的中點

求鏈表中點的方法
使用兩個指針fast,low, fast和low同時向前跳, fast每次向前跳兩個節(jié)點, low每次向前跳一個節(jié)點,當(dāng)fast調(diào)到尾部的時候,low就指向了中點
相關(guān)題目

四,鏈表環(huán)的問題
  • 1,鏈表是否存在環(huán)?
  • 2,鏈表環(huán)的入口節(jié)點?
  • 3,鏈表中存在環(huán),環(huán)的長度?
  • 1,對于問題1
    我們可以使用兩個指針fast,low, fast每次前進兩步,low每次前進一次,如果fast和low都到鏈表尾部且為空,則不在環(huán)如果fast和low第一次相遇到某一節(jié)點,且不為空,則存在環(huán).

  • 2,對于問題2
    若存在環(huán),第一次相遇后, 將fast指向頭結(jié)點,然后fast和low都每次向前移動一步,那么再次相交的節(jié)點就是環(huán)的入口節(jié)點

  • 3,對于問題3
    假設(shè)頭結(jié)點到環(huán)的入口節(jié)點為A, 環(huán)的入口節(jié)點到fast和low第一次相遇的節(jié)點距離為B, 環(huán)的長度為C.
    我們可以得出如下推論:
    1)第一次相遇時,low走過的長度是 A+B, fast走過的長度是2(A+B)
    2)fast比low走的距離剛好多環(huán)一周C.
    所以 2(A+B) - (A+B) = C ====> A+B = C

由上可知,當(dāng)fast和low第一次相遇后, 將fast指向頭節(jié)點,然后fast每次前進一步,而low不動,當(dāng)其到達low指向的節(jié)點時,走過的長度就是環(huán)的周長

鏈表環(huán).jpg
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市荧呐,隨后出現(xiàn)的幾起案子卜录,更是在濱河造成了極大的恐慌水醋,老刑警劉巖型凳,帶你破解...
    沈念sama閱讀 222,807評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件寥枝,死亡現(xiàn)場離奇詭異,居然都是意外死亡,警方通過查閱死者的電腦和手機养晋,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來梁钾,“玉大人绳泉,你說我怎么就攤上這事∧沸海” “怎么了零酪?”我有些...
    開封第一講書人閱讀 169,589評論 0 363
  • 文/不壞的土叔 我叫張陵,是天一觀的道長拇勃。 經(jīng)常有香客問我四苇,道長,這世上最難降的妖魔是什么方咆? 我笑而不...
    開封第一講書人閱讀 60,188評論 1 300
  • 正文 為了忘掉前任月腋,我火速辦了婚禮,結(jié)果婚禮上瓣赂,老公的妹妹穿的比我還像新娘榆骚。我一直安慰自己,他們只是感情好煌集,可當(dāng)我...
    茶點故事閱讀 69,185評論 6 398
  • 文/花漫 我一把揭開白布妓肢。 她就那樣靜靜地躺著,像睡著了一般苫纤。 火紅的嫁衣襯著肌膚如雪碉钠。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,785評論 1 314
  • 那天卷拘,我揣著相機與錄音喊废,去河邊找鬼。 笑死恭金,一個胖子當(dāng)著我的面吹牛操禀,可吹牛的內(nèi)容都是我干的褂策。 我是一名探鬼主播横腿,決...
    沈念sama閱讀 41,220評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼斤寂!你這毒婦竟也來了耿焊?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,167評論 0 277
  • 序言:老撾萬榮一對情侶失蹤遍搞,失蹤者是張志新(化名)和其女友劉穎罗侯,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體溪猿,經(jīng)...
    沈念sama閱讀 46,698評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡钩杰,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,767評論 3 343
  • 正文 我和宋清朗相戀三年纫塌,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片讲弄。...
    茶點故事閱讀 40,912評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡措左,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出避除,到底是詐尸還是另有隱情怎披,我是刑警寧澤,帶...
    沈念sama閱讀 36,572評論 5 351
  • 正文 年R本政府宣布瓶摆,位于F島的核電站凉逛,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏群井。R本人自食惡果不足惜状飞,卻給世界環(huán)境...
    茶點故事閱讀 42,254評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望蝌借。 院中可真熱鬧昔瞧,春花似錦、人聲如沸菩佑。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽稍坯。三九已至酬荞,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間瞧哟,已是汗流浹背混巧。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留勤揩,地道東北人咧党。 一個月前我還...
    沈念sama閱讀 49,359評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像陨亡,于是被迫代替她去往敵國和親傍衡。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,922評論 2 361

推薦閱讀更多精彩內(nèi)容

  • //leetcode中還有花樣鏈表題负蠕,這里幾個例子蛙埂,冰山一角 求單鏈表中結(jié)點的個數(shù)----時間復(fù)雜度O(n)這是最...
    暗黑破壞球嘿哈閱讀 1,521評論 0 6
  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪:刷leetcod...
    土汪閱讀 12,749評論 0 33
  • LeetCode 刷題隨手記 - 第一部分 前 256 題(非會員)遮糖,僅算法題绣的,的吐槽 https://leetc...
    蕾娜漢默閱讀 17,819評論 2 36
  • Single Linked List 相比較另一個基本的數(shù)據(jù)結(jié)構(gòu)array,linked list有幾個優(yōu)勢:尺寸...
    dol_re_mi閱讀 8,194評論 0 3
  • 2. Add Two Numbers 先初始化兩個結(jié)點,一個用來做head屡江,一個作為指引node不斷向下延續(xù)的指針...
    Morphiaaa閱讀 922評論 0 0