一、理解指針或引用的含義

1.含義：將某個變量（對象）賦值給指針（引用），實際上就是就是將這個變量（對象）的地址賦值給指針（引用）。

2.示例：

p—>next = q; 表示p節(jié)點的后繼指針存儲了q節(jié)點的內存地址。

p—>next = p—>next—>next; 表示p節(jié)點的后繼指針存儲了p節(jié)點的下下個節(jié)點的內存地址。

二、警惕指針丟失和內存泄漏（單鏈表）

1.插入節(jié)點

在節(jié)點a和節(jié)點b之間插入節(jié)點x，b是a的下一節(jié)點，，p指針指向節(jié)點a，則造成指針丟失和內存泄漏的代碼：p—>next = x;x—>next = p—>next; 顯然這會導致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è)務邏輯。如果我們引入“哨兵”節(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é)點都可以統(tǒng)一為相同的代碼實現(xiàn)邏輯了。

4.“哨兵”還有哪些應用場景？

這個知識有限，暫時想不出來呀！但總結起來，哨兵最大的作用就是簡化邊界條件的處理。

四、重點留意邊界條件處理

經常用來檢查鏈表是否正確的邊界4個邊界條件：

1.如果鏈表為空時，代碼是否能正常工作？

2.如果鏈表只包含一個節(jié)點時，代碼是否能正常工作？

3.如果鏈表只包含兩個節(jié)點時，代碼是否能正常工作？

4.代碼邏輯在處理頭尾節(jié)點時是否能正常工作？

五、舉例畫圖，輔助思考

核心思想：釋放腦容量，留更多的給邏輯思考，這樣就會感覺到思路清晰很多。

六、多寫多練，沒有捷徑

5個常見的鏈表操作：

1.單鏈表反轉

2.鏈表中環(huán)的檢測

3.兩個有序鏈表合并

4.刪除鏈表倒數(shù)第n個節(jié)點

5.求鏈表的中間節(jié)點