前言
我們接著上部分的二分查找，再繼續鏈表相關的題目
換一個角度來理解鏈表
我相信大家對鏈表的資料結構已經很熟悉了，什么單鏈表，回圈鏈表，雙向鏈表，雙向回圈鏈表，
我們這里以java的層面來理解指標或參考的含義：
實際上，鏈表其實并不復雜，復雜的是我們很容易將它和指標混淆在一起，就會讓人產生疑惑，所以想要寫好鏈表的代碼，就得拋開舊識，重新理解指標，
我們知道，有些語言有“指標”的概念，比如 C 語言；有些語言沒有指標，取而代之的是“參考”，比如 Java、Python，不管是“指標”還是“參考”，實際上，它們的意思都是一樣的，都是存盤所指物件的記憶體地址，
所以作為java程式員，我們要牢牢記住，什么是參考：
將某個變數賦值給參考，實際上就是將這個變數的地址賦值給參考，或者反過來說，參考中存盤了這個變數的記憶體地址，指向了這個變數，通過參考就能找到這個變數，
如下面這段代碼，就是一個鏈表結構的物件，當我們在呼叫參考移來移去的時候，你要牢牢記住，自己操作的是這個物件，其他參考該物件的都會收到影響，
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
解題技巧
警惕指標丟失
初學者寫鏈表的時候，最容易犯的錯誤就是，常常把指標給搞丟了，
我們以向鏈表(a->b->c-null)插入節點來實體：
a.next = x;
x.next = a.next;
我一開始寫鏈表代碼的時候也經常犯這種錯誤，值得注意的是，當我們呼叫第一行代碼的時候，a的next節點已經指向了x，此時記憶體中存在兩個鏈表
a->x->null
b->c->null
當呼叫第二行代碼的時候，x的next節點又指向了自己，
所以，我們插入結點時，一定要注意操作的順序，要先將結點 x 的 next 參考指向結點 b，再把結點 a 的 next 參考指向結點 x，這樣才不會丟失指標，
利用哨兵簡化實作難度
我給出一段代碼，就是鏈表的插入操作
newNode.next = p.next;
p.next = newNode;
但是，如果我們要插入鏈表中的第一個結點，前面的代碼就不 work 了，我們需要對于這種情況特殊處理，寫成代碼是這樣子的：
if (head == null) {
head = newNode;
}
針對鏈表的插入、洗掉操作，需要對插入第一個結點和洗掉最后一個結點的情況進行特殊處理，這樣代碼實作起來就會很繁瑣，不簡潔，而且也容易因為考慮不全而出錯，如何來解決這個問題呢？
“哨兵”節點不存盤資料，無論鏈表是否為空，head指標都會指向它，作為鏈表的頭結點始終存在，這樣，插入第一個節點和插入其他節點，洗掉最后一個節點和洗掉其他節點都可以統一為相同的代碼實作邏輯了，
重點留意邊界條件處理
我每次寫鏈表相關問題的時候，都會優先判斷幾個條件，看我的代碼是否能正常work
- 如果鏈表為空時，代碼是否能正常作業？
- 如果鏈表只包含一個結點時，代碼是否能正常作業？
- 如果鏈表只包含兩個結點時，代碼是否能正常作業？
- 代碼邏輯在處理頭結點和尾結點的時候，是否能正常作業？
當你寫完鏈表代碼之后，除了看下你寫的代碼在正常的情況下能否作業，還要看下在上面我列舉的幾個邊界條件下，代碼仍然能否正確作業，如果這些邊界條件下都沒有問題，那基本上可以認為沒有問題了，
用遞回來解決問題
有些時候，我們可以用遞回來解決相關的題目可能效果會更好，當然后面會有一篇專門來講解遞回相關的題目，
我們這里用一道很基礎的題目來示例，鏈表反轉
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode lastNode = reverseList(head.next);
head.next.next = head;
head.next = null;
return lastNode;
}
看起來是不是感覺不知所云，完全不能理解這樣為什么能夠反轉鏈表？我們下面來詳細解釋一下這段代碼，
對于遞回演算法，最重要的就是明確遞回函式的定義，具體來說，我們的 reverseList 函式定義是這樣的：
輸入一個節點 head，將「以 head 為起點」的鏈表反轉，并回傳反轉之后的頭結點，
明白了函式的定義，在來看這個問題，比如說我們想反轉這個鏈表：
1->2->3->4 (head指向1)
那么輸入 reverse(head) 后，會在這里進行遞回（）：
ListNode last = reverse(head.next);
不要跳進遞回（你的腦袋能壓幾個堆疊呀？），而是要根據剛才的函式定義，來弄清楚這段代<碼產<生么結果：
1->2<-3<-4 (head指向1,lastNode指向4)
然后執行：
head.next.next = head;
head.next = null;
此時鏈表將變成：
1<-2<-3<-4
神奇不，鏈表在此時就成功的反轉了，所以掌握遞回解法也是很重要的，很多很復雜的指標解法，換個思路說不定也會非常的簡單，
總結
寫鏈表代碼是最考驗邏輯思維能力的，寫的時候一定要考慮全面，最好將我剛才說的容易錯的情況都在腦子里過一遍，
對于部分題解，換個思路使用遞回，可能會簡單很多，
多看，多練，多思考
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/225974.html
標籤：其他
上一篇：讓鏈表題目不再復雜