怎么寫好鏈表代碼

1. 理解指針或引用的含義
   指針存儲了指定變量的內(nèi)存地址，通過指針就能找到這個變量
   p -> next = q代表p節(jié)點的next指針中存儲了q節(jié)點的內(nèi)存地址
   常用的還有p->next=p->next->next 直接把p的next指針指向p節(jié)點的下下一個加點的內(nèi)存

2. 警惕指針丟失和內(nèi)存泄露
   插入節(jié)點時一定要注意操作順序，在a、b節(jié)點中插入c節(jié)點時，必須先把c的next指向b，再把a的next指向c。
   同時刪除鏈表節(jié)點時也記得手動釋放內(nèi)存空間。

3. 利用哨兵簡化實現(xiàn)難度
   無論插入鏈表的第一個節(jié)點還是刪除鏈表的最后一個節(jié)點，我們都需要特殊處理，為了避免和簡化操作，引入了哨兵概念。它不參與業(yè)務(wù)邏輯，只解決邊界問題。
   如果鏈表中存在哨兵節(jié)點，它會被稱作帶頭鏈表，相反，沒有哨兵節(jié)點的鏈表被叫做不帶頭鏈表。
   

   image.png

4. 重點留意邊界

   • 如果鏈表為空，代碼是否正常？
   • 如果鏈表只有一個節(jié)點，代碼是否正常？
   • 如果鏈表只有兩個節(jié)點時，代碼是否正常？
   • 代碼處理頭結(jié)點和尾結(jié)點時，是否正常？

5. 舉例畫圖，輔助思考
   在寫的同時在草稿上列出具體內(nèi)容或者畫出相關(guān)的節(jié)點增減，這能有效幫助構(gòu)筑具體的操作步驟

6. 多寫多練，沒有捷徑
   多寫，熟練以下內(nèi)容

   • 單鏈表反轉(zhuǎn) 206
   • 鏈表中環(huán)的檢測 141
   • 兩個有序的鏈表合并 21
   • 刪除鏈表倒數(shù)第 n 個結(jié)點 19
   • 求鏈表的中間結(jié)點 876

此文章為2月Day4學(xué)習(xí)筆記，內(nèi)容來源與極客時間《數(shù)據(jù)結(jié)構(gòu)與算法之美》