0 如何優(yōu)雅的寫出鏈表代碼怖糊？6大學習技巧
一、理解指針或引用的含義
1.含義：將某個變量（對象）賦值給指針（引用），實際上就是就是將這個變量（對象）的地址賦值給指針（引用）。
2.示例：
p—>next = q; 表示p節(jié)點的后繼指針存儲了q節(jié)點的內(nèi)存地址即供。
p—>next = p—>next—>next; 表示p節(jié)點的后繼指針存儲了p節(jié)點的下下個節(jié)點的內(nèi)存地址。
二、警惕指針丟失和內(nèi)存泄漏（單鏈表）
1.插入節(jié)點
在節(jié)點a和節(jié)點b之間插入節(jié)點x，b是a的下一節(jié)點撑瞧，，p指針指向節(jié)點a显蝌，則造成指針丟失和內(nèi)存泄漏的代碼：p—>next = x;x—>next = p—>next; 顯然這會導(dǎo)致x節(jié)點的后繼指針指向自身预伺。
正確的寫法是2句代碼交換順序，即：x—>next = p—>next; p—>next = x;
2.刪除節(jié)點
在節(jié)點a和節(jié)點b之間刪除節(jié)點b曼尊，b是a的下一節(jié)點酬诀，p指針指向節(jié)點a：p—>next = p—>next—>next;
三、利用“哨兵”簡化實現(xiàn)難度
1.什么是“哨兵”骆撇？
鏈表中的“哨兵”節(jié)點是解決邊界問題的瞒御，不參與業(yè)務(wù)邏輯。如果我們引入“哨兵”節(jié)點艾船，則不管鏈表是否為空葵腹，head指針都會指向這個“哨兵”節(jié)點高每。我們把這種有“哨兵”節(jié)點的鏈表稱為帶頭鏈表屿岂，相反践宴，沒有“哨兵”節(jié)點的鏈表就稱為不帶頭鏈表。
2.未引入“哨兵”的情況如果在p節(jié)點后插入一個節(jié)點爷怀，只需2行代碼即可搞定：
new_node—>next = p—>next;
p—>next = new_node;
但阻肩，若向空鏈表中插入一個節(jié)點，則代碼如下：
if(head == null){
head = new_node;
}
如果要刪除節(jié)點p的后繼節(jié)點运授，只需1行代碼即可搞定：
p—>next = p—>next—>next;
但烤惊，若是刪除鏈表的最有一個節(jié)點（鏈表中只剩下這個節(jié)點），則代碼如下：
if(head—>next == null){
head = null;
}
從上面的情況可以看出吁朦，針對鏈表的插入柒室、刪除操作，需要對插入第一個節(jié)點和刪除最后一個節(jié)點的情況進行特殊處理逗宜。這樣代碼就會顯得很繁瑣雄右，所以引入“哨兵”節(jié)點來解決這個問題。
3.引入“哨兵”的情況
“哨兵”節(jié)點不存儲數(shù)據(jù)纺讲，無論鏈表是否為空擂仍，head指針都會指向它，作為鏈表的頭結(jié)點始終存在熬甚。這樣逢渔，插入第一個節(jié)點和插入其他節(jié)點，刪除最后一個節(jié)點和刪除其他節(jié)點都可以統(tǒng)一為相同的代碼實現(xiàn)邏輯了乡括。
4.“哨兵”還有哪些應(yīng)用場景肃廓？
這個知識有限，暫時想不出來呀诲泌！但總結(jié)起來盲赊，哨兵最大的作用就是簡化邊界條件的處理。四档礁、重點留意邊界條件處理
經(jīng)常用來檢查鏈表是否正確的邊界4個邊界條件：
1.如果鏈表為空時角钩，代碼是否能正常工作？
2.如果鏈表只包含一個節(jié)點時呻澜，代碼是否能正常工作递礼？
3.如果鏈表只包含兩個節(jié)點時，代碼是否能正常工作羹幸？
4.代碼邏輯在處理頭尾節(jié)點時是否能正常工作脊髓？
五、舉例畫圖栅受，輔助思考
核心思想：釋放腦容量将硝，留更多的給邏輯思考恭朗，這樣就會感覺到思路清晰很多。
六依疼、多寫多練痰腮，沒有捷徑
5個常見的鏈表操作：
1.單鏈表反轉(zhuǎn)
2.鏈表中環(huán)的檢測
3.兩個有序鏈表合并
4.刪除鏈表倒數(shù)第n個節(jié)點
5.求鏈表的中間節(jié)點
1 棧
一、什么是棧律罢？
1.后進者先出膀值，先進者后出，這就是典型的“椢蠹”結(jié)構(gòu)沧踏。
2.從棧的操作特性來看，是一種“操作受限”的線性表巾钉，只允許在端插入和刪除數(shù)據(jù)翘狱。
二、為什么需要棧砰苍？
1.棧是一種操作受限的數(shù)據(jù)結(jié)構(gòu)潦匈，其操作特性用數(shù)組和鏈表均可實現(xiàn)。
2.但师骗，任何數(shù)據(jù)結(jié)構(gòu)都是對特定應(yīng)用場景的抽象历等，數(shù)組和鏈表雖然使用起來更加靈活，但卻暴露了幾乎所有的操作辟癌，難免會引發(fā)錯誤操作的風險寒屯。
3.所以，當某個數(shù)據(jù)集合只涉及在某端插入和刪除數(shù)據(jù)黍少，且滿足后進者先出寡夹，先進者后出的操作特性時，我們應(yīng)該首選棧這種數(shù)據(jù)結(jié)構(gòu)厂置。
三菩掏、如何實現(xiàn)棧？
1.棧的API
public class Stack<Item> {
//壓棧
public void push(Item item){}
//彈棧
public Item pop(){}
//是否為空
public boolean isEmpty(){}
//棧中數(shù)據(jù)的數(shù)量
public int size(){}
//返回棧中最近添加的元素而不刪除它
public Item peek(){}}
2.數(shù)組實現(xiàn)（自動擴容）
時間復(fù)雜度分析：根據(jù)均攤復(fù)雜度的定義昵济，可以得數(shù)組實現(xiàn)（自動擴容）符合大多數(shù)情況是O(1)級別復(fù)雜度智绸，個別情況是O(n)級別復(fù)雜度，比如自動擴容時访忿，會進行完整數(shù)據(jù)的拷貝瞧栗。
空間復(fù)雜度分析：在入棧和出棧的過程中，只需要一兩個臨時變量存儲空間海铆，所以O(shè)(1)級別迹恐。我們說空間復(fù)雜度的時候，是指除了原本的數(shù)據(jù)存儲空間外卧斟，算法運行還需要額外的存儲空間殴边。
實現(xiàn)代碼：（見另一條留言）
3.鏈表實現(xiàn)
時間復(fù)雜度分析：壓棧和彈棧的時間復(fù)雜度均為O(1)級別憎茂，因為只需更改單個節(jié)點的索引即可。
空間復(fù)雜度分析：在入棧和出棧的過程中锤岸，只需要一兩個臨時變量存儲空間竖幔，所以O(shè)(1)級別。我們說空間復(fù)雜度的時候能耻，是指除了原本的數(shù)據(jù)存儲空間外赏枚，算法運行還需要額外的存儲空間亡驰。
實現(xiàn)代碼：（見另一條留言）
四晓猛、棧的應(yīng)用
1.棧在函數(shù)調(diào)用中的應(yīng)用
操作系統(tǒng)給每個線程分配了一塊獨立的內(nèi)存空間，這塊內(nèi)存被組織成“椃踩瑁”這種結(jié)構(gòu)戒职，用來存儲函數(shù)調(diào)用時的臨時變量。每進入一個函數(shù)透乾，就會將其中的臨時變量作為棧幀入棧洪燥，當被調(diào)用函數(shù)執(zhí)行完成，返回之后乳乌，將這個函數(shù)對應(yīng)的棧幀出棧捧韵。2.棧在表達式求值中的應(yīng)用（比如：34+13*9+44-12/3）
利用兩個棧，其中一個用來保存操作數(shù)汉操，另一個用來保存運算符再来。我們從左向右遍歷表達式，當遇到數(shù)字磷瘤，我們就直接壓入操作數(shù)棧芒篷；當遇到運算符，就與運算符棧的棧頂元素進行比較采缚，若比運算符棧頂元素優(yōu)先級高针炉，就將當前運算符壓入棧，若比運算符棧頂元素的優(yōu)先級低或者相同扳抽，從運算符棧中取出棧頂運算符篡帕，從操作數(shù)棧頂取出2個操作數(shù)，然后進行計算贸呢，把計算完的結(jié)果壓入操作數(shù)棧镰烧，繼續(xù)比較。
3.棧在括號匹配中的應(yīng)用（比如：{}{()}）
用棧保存為匹配的左括號贮尉，從左到右一次掃描字符串拌滋，當掃描到左括號時，則將其壓入棧中猜谚；當掃描到右括號時败砂，從棧頂取出一個左括號赌渣，如果能匹配上，則繼續(xù)掃描剩下的字符串昌犹。如果掃描過程中坚芜，遇到不能配對的右括號，或者棧中沒有數(shù)據(jù)斜姥，則說明為非法格式鸿竖。
當所有的括號都掃描完成之后，如果棧為空铸敏，則說明字符串為合法格式缚忧；否則，說明未匹配的左括號為非法格式杈笔。
4.如何實現(xiàn)瀏覽器的前進后退功能闪水？
我們使用兩個棧X和Y，我們把首次瀏覽的頁面依次壓如棧X蒙具，當點擊后退按鈕時球榆，再依次從棧X中出棧，并將出棧的數(shù)據(jù)一次放入Y棧禁筏。當點擊前進按鈕時持钉，我們依次從棧Y中取出數(shù)據(jù)，放入棧X中篱昔。當棧X中沒有數(shù)據(jù)時每强，說明沒有頁面可以繼續(xù)后退瀏覽了。當Y棧沒有數(shù)據(jù)旱爆，那就說明沒有頁面可以點擊前進瀏覽了舀射。
五、思考
- 我們在講棧的應(yīng)用時怀伦，講到用函數(shù)調(diào)用棧來保存臨時變量脆烟，為什么函數(shù)調(diào)用要用“棧”來保存臨時變量呢房待？用其他數(shù)據(jù)結(jié)構(gòu)不行嗎邢羔？
答：因為函數(shù)調(diào)用的執(zhí)行順序符合后進者先出，先進者后出的特點桑孩。比如函數(shù)中的局部變量的生命周期的長短是先定義的生命周期長拜鹤，后定義的生命周期短；還有函數(shù)中調(diào)用函數(shù)也是這樣流椒，先開始執(zhí)行的函數(shù)只有等到內(nèi)部調(diào)用的其他函數(shù)執(zhí)行完畢敏簿，該函數(shù)才能執(zhí)行結(jié)束。正是由于函數(shù)調(diào)用的這些特點，根據(jù)數(shù)據(jù)結(jié)構(gòu)是特定應(yīng)用場景的抽象的原則惯裕，我們優(yōu)先考慮棧結(jié)構(gòu)温数。
2.我們都知道，JVM 內(nèi)存管理中有個“堆楎呤疲”的概念撑刺。棧內(nèi)存用來存儲局部變量和方法調(diào)用，堆內(nèi)存用來存儲 Java 中的對象握玛。那 JVM 里面的“椆话”跟我們這里說的“棧”是不是一回事呢挠铲？如果不是冕屯，那它為什么又叫作“棧”呢市殷？
答：JVM里面的棧和我們這里說的是一回事愕撰，被稱為方法棧。和前面函數(shù)調(diào)用的作用是一致的醋寝，用來存儲方法中的局部變量。
2 隊列
2.1 隊列的種類
- 順序隊列带迟，鏈式隊列
- 單向隊列音羞，循環(huán)隊列
- 并發(fā)隊列（線程安全的隊列稱為并發(fā)隊列），阻塞隊列（隊列為空時取數(shù)據(jù)會被阻塞仓犬，隊滿時增加數(shù)據(jù)會被阻塞）
2.2 隊列的邊界條件
單向隊列：隊空：head == tail 隊滿： head == 0 && tail == n
循環(huán)隊列：tail指針指向最后一個元素的下一個位置嗅绰，即指向了一個空。隊空：head == tail 隊滿：(tail+1)%n == head
2.3 CAS無鎖機制并發(fā)隊列
CAS算法包含三個參數(shù)V（要更新的變量現(xiàn)在的值）搀继，E（要更新的變量期望的值）窘面，N（新的值）。僅當V == E時叽躯，則將變量更新為N并返回财边，若V != E，則表示已經(jīng)有其他線程動過這個變量了点骑，則什么都不做且返回當前V的真實值酣难。
CAS總是抱著樂觀的態(tài)度，認為自己可以成功更新V黑滴，但多個線程競爭時憨募，只有一個線程會勝出。失敗的線程不會被掛起袁辈，可以取消操作也可以允許繼續(xù)嘗試菜谣。基于這樣的原理，就算是多線程并發(fā)尾膊，也可以正常處理并發(fā)操作甘磨。
3 遞歸
3.1 什么是遞歸？
1.遞歸是一種非常高效眯停、簡潔的編碼技巧济舆，一種應(yīng)用非常廣泛的算法，比如DFS深度優(yōu)先搜索莺债、前中后序二叉樹遍歷等都是使用遞歸滋觉。
2.方法或函數(shù)調(diào)用自身的方式稱為遞歸調(diào)用，調(diào)用稱為遞齐邦，返回稱為歸椎侠。
3.基本上，所有的遞歸問題都可以用遞推公式來表示措拇，比如
f(n) = f(n-1) + 1;
f(n) = f(n-1) + f(n-2);
f(n)=n*f(n-1);
3.2 為什么使用遞歸我纪？遞歸的優(yōu)缺點？
1.優(yōu)點：代碼的表達力很強丐吓，寫起來簡潔浅悉。
2.缺點：空間復(fù)雜度高、有堆棧溢出風險券犁、存在重復(fù)計算术健、過多的函數(shù)調(diào)用會耗時較多等問題。
3.3 什么樣的問題可以用遞歸解決呢粘衬？
一個問題只要同時滿足以下3個條件荞估，就可以用遞歸來解決：
1.問題的解可以分解為幾個子問題的解。何為子問題稚新？就是數(shù)據(jù)規(guī)模更小的問題勘伺。
2.問題與子問題，除了數(shù)據(jù)規(guī)模不同褂删，求解思路完全一樣
3.存在遞歸終止條件
3.4 如何實現(xiàn)遞歸飞醉？
1.遞歸代碼編寫
寫遞歸代碼的關(guān)鍵就是找到如何將大問題分解為小問題的規(guī)律，并且基于此寫出遞推公式笤妙，然后再推敲終止條件冒掌，最后將遞推公式和終止條件翻譯成代碼。
2.遞歸代碼理解
對于遞歸代碼蹲盘，若試圖想清楚整個遞和歸的過程股毫，實際上是進入了一個思維誤區(qū)。
那該如何理解遞歸代碼呢召衔？如果一個問題A可以分解為若干個子問題B铃诬、C、D，你可以假設(shè)子問題B趣席、C兵志、D已經(jīng)解決。而且宣肚，你只需要思考問題A與子問題B想罕、C、D兩層之間的關(guān)系即可霉涨，不需要一層層往下思考子問題與子子問題按价，子子問題與子子子問題之間的關(guān)系。屏蔽掉遞歸細節(jié)笙瑟，這樣子理解起來就簡單多了楼镐。
因此，理解遞歸代碼往枷，就把它抽象成一個遞推公式框产，不用想一層層的調(diào)用關(guān)系，不要試圖用人腦去分解遞歸的每個步驟错洁。
3.5 遞歸常見問題及解決方案
1.警惕堆棧溢出：可以聲明一個全局變量來控制遞歸的深度秉宿，從而避免堆棧溢出。
2.警惕重復(fù)計算：通過某種數(shù)據(jù)結(jié)構(gòu)來保存已經(jīng)求解過的值墓臭，從而避免重復(fù)計算蘸鲸。
3.6 如何將遞歸改寫為非遞歸代碼？
籠統(tǒng)的講窿锉，所有的遞歸代碼都可以改寫為迭代循環(huán)的非遞歸寫法。如何做膝舅？抽象出遞推公式嗡载、初始值和邊界條件，然后用迭代循環(huán)實現(xiàn)仍稀。
一樣一樣
