一,單鏈表的創(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)的周長
