如何輕鬆寫出正確的連結串列程式碼？

摘要： 理解指標或引用的含義 含義：將某個變數（物件）賦值給指標（引用），實際上就是就是將這個變數（物件）的地址賦值給指標（引用）。 示例：p—>next = q; 表示p節點的後繼指標儲存了q節點的記憶體地址。p—>next = p—>next—>...

理解指標或引用的含義

• 含義：將某個變數（物件）賦值給指標（引用），實際上就是就是將這個變數（物件）的地址賦值給指標（引用）。
• 示例：
  p—>next = q; 表示p節點的後繼指標儲存了q節點的記憶體地址。
  p—>next = p—>next—>next; 表示p節點的後繼指標儲存了p節點的下下個節點的記憶體地址。

警惕指標丟失和記憶體洩漏（單鏈表）

• 插入節點
  在節點a和節點b之間插入節點x，b是a的下一節點，，p指標指向節點a，則造成指標丟失和記憶體洩漏的程式碼：p—>next = x;x—>next = p—>next; 顯然這會導致x節點的後繼指標指向自身。
  正確的寫法是2句程式碼交換順序，即：x—>next = p—>next; p—>next = x;
• 刪除節點
  在節點a和節點b之間刪除節點b，b是a的下一節點，p指標指向節點a：p—>next = p—>next—>next;

利用“哨兵”簡化實現難度

• 什麼是“哨兵”？
  連結串列中的“哨兵”節點是解決邊界問題的，不參與業務邏輯。如果我們引入“哨兵”節點，則不管連結串列是否為空，head指標都會指向這個“哨兵”節點。我們把這種有“哨兵”節點的連結串列稱為帶頭連結串列，相反，沒有“哨兵”節點的連結串列就稱為不帶頭連結串列。
• 未引入“哨兵”的情況
  如果在p節點後插入一個節點，只需2行程式碼即可搞定：
  new_node—>next = p—>next;
  p—>next = new_node;
  但，若向空連結串列中插入一個節點，則程式碼如下：
  if(head == null){
  head = new_node;
  }
  如果要刪除節點p的後繼節點，只需1行程式碼即可搞定：
  p—>next = p—>next—>next;
  但，若是刪除連結串列的最有一個節點（連結串列中只剩下這個節點），則程式碼如下：
  if(head—>next == null){
  head = null;
  }
  從上面的情況可以看出，針對連結串列的插入、刪除操作，需要對插入第一個節點和刪除最後一個節點的情況進行特殊處理。這樣程式碼就會顯得很繁瑣，所以引入“哨兵”節點來解決這個問題。
• 引入“哨兵”的情況
  “哨兵”節點不儲存資料，無論連結串列是否為空，head指標都會指向它，作為連結串列的頭結點始終存在。這樣，插入第一個節點和插入其他節點，刪除最後一個節點和刪除其他節點都可以統一為相同的程式碼實現邏輯了。
• “哨兵”還有哪些應用場景？
  這個知識有限，暫時想不出來呀！但總結起來，哨兵最大的作用就是簡化邊界條件的處理。

重點留意邊界條件處理

經常用來檢查連結串列是否正確的邊界4個邊界條件：

• 1.如果連結串列為空時，程式碼是否能正常工作？
• 2.如果連結串列只包含一個節點時，程式碼是否能正常工作？
• 3.如果連結串列只包含兩個節點時，程式碼是否能正常工作？
• 4.程式碼邏輯在處理頭尾節點時是否能正常工作？

舉例畫圖，輔助思考

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

多寫多練，沒有捷徑

• 1.單鏈表反轉
• 2.連結串列中環的檢測
• 3.兩個有序連結串列合併
• 4.刪除連結串列倒數第n個節點
• 5.求連結串列的中間節點