技巧一：理解指針或引用的含義

將某個變量賦值給指針，實際上就是將這個變量的地址賦值給指針，或者反過來說，指針中存儲了這個變量的內存地址，指向了這個變量，通過指針就能找到這個變量。

常見鏈表代碼

p->next=q

這行代碼是說，p結點的next指針存儲了q結點的內存地址。

p->next=p->next->next

這行代碼表示，p結點的next指針存儲了p結點的下下一個結點的內存地址。

技巧二：警惕指針丟失和內存泄漏

單鏈表的插入操作

p->next = x;  // 將p的next指針指向x結點；
x->next = p->next;  // 將x的結點的next指針指向b結點；

在上面這段代碼中，p->next 指針在完成第一步操作之后，已經不再指向結點b了，而是指向結點x。第二行代碼相當于將x賦值給x->next，自己指向自己。因此，整個鏈表也就斷成了兩半，從結點b往后的所有結點都無法訪問到了。
x->next=p->next; 而p->next=x; 所以 x->next=p->next;等價于x->next=x; 所以指針斷裂，x節點之后的節點丟失了。
上面代碼只要將第1行和第2行代碼顛倒下就OK了。

• 插入結點時，一定要注意操作的順序
• 刪除鏈表結點時，也一定要記得手動釋放內存空間

技巧三：利用哨兵簡化實現難度

單鏈表的插入和刪除操作

在結點p后面插入一個新的結點

new_node->next = p->next;
p->next = new_node;

空鏈表中插入第一個結點

if (head == null) {
  head = new_node;
}

刪除結點p的后繼結點

p->next = p->next->next;

刪除鏈表中的最后一個結點

if (head->next == null) {
   head = null;
}

針對鏈表的插入、刪除操作，需要對插入第一個結點和刪除最后一個結點的情況進行特殊處理。

哨兵，解決的是國家之間的邊界問題。同理，這里說的哨兵也是解決“邊界問題”的，不直接參與業務邏輯。

head=null表示一個空鏈表，如果引入哨兵結點，在任何時候，不管鏈表是不是空，head指針都會一直指向這個哨兵結點。我們把這種有哨兵結點的鏈表叫帶頭鏈表，沒有哨兵結點的鏈表叫作不帶頭鏈表。

哨兵結點是不存儲數據的。因為哨兵結點一直存在，所有插入第一個結點和插入其他結點，刪除最后一個結點和刪除其他結點，都可以統一為相同的代碼實現邏輯了。
這種利用哨兵簡化編程難度的技巧，在很多代碼實現中都有用到，比如插入排序、歸并排序、動態規劃等。

哨兵實現代碼

代碼一

// 在數組a中，查找key，返回key所在的位置
// 其中，n表示數組a的長度
int find(char* a, int n, char key) {
  // 邊界條件處理，如果a為空，或者n<=0，說明數組中沒有數據，就不用while循環比較了
  if(a == null || n <= 0) {
    return -1;
  }
  
  int i = 0;
  // 這里有兩個比較操作：i<n和a[i]==key.
  while (i < n) {
    if (a[i] == key) {
      return i;
    }
    ++i;
  }
  
  return -1;
}

代碼二

// 在數組a中，查找key，返回key所在的位置
// 其中，n表示數組a的長度
// 我舉2個例子，你可以拿例子走一下代碼
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 7
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 6
int find(char* a, int n, char key) {
  if(a == null || n <= 0) {
    return -1;
  }
  
  // 這里因為要將a[n-1]的值替換成key，所以要特殊處理這個值
  if (a[n-1] == key) {
    return n-1;
  }
  
  // 把a[n-1]的值臨時保存在變量tmp中，以便之后恢復。tmp=6。
  // 之所以這樣做的目的是：希望find()代碼不要改變a數組中的內容
  char tmp = a[n-1];
  // 把key的值放到a[n-1]中，此時a = {4, 2, 3, 5, 9, 7}
  a[n-1] = key;
  
  int i = 0;
  // while 循環比起代碼一，少了i<n這個比較操作
  while (a[i] != key) {
    ++i;
  }
  
  // 恢復a[n-1]原來的值,此時a= {4, 2, 3, 5, 9, 6}
  a[n-1] = tmp;
  
  if (i == n-1) {
    // 如果i == n-1說明，在0...n-2之間都沒有key，所以返回-1
    return -1;
  } else {
    // 否則，返回i，就是等于key值的元素的下標
    return i;
  }
}

第二段代碼中，我們通過一個哨兵 a[n-1] = key，成功省掉了一個比較語句 i<n，因此，當字符串a很長的時候，比如幾萬、幾十萬次時，第二段代碼運行的更快（因為兩段代碼中執行次數最多的是while循環那部分）。

技巧四：重點留意邊界條件處理

常用的用來檢查鏈表代碼是否正確的邊界條件：

• 如果鏈表為空時，代碼是否能正常工作？
• 如果鏈表只包含一個結點時，代碼是否能正常工作？
• 如果鏈表只包含兩個結點時，代碼是否能正常工作？
• 代碼邏輯在處理頭結點和尾結點的時候，是否能正常工作？

技巧五：舉例畫圖，輔助思考

技巧六：多寫多練，沒有捷徑

5個常見的鏈表操作

• 單鏈表反轉
• 鏈表中環的檢測
• 兩個有序的鏈表合并
• 刪除鏈表倒數第 n 個結點
• 求鏈表的中間結點

練習題LeetCode對應編號：206，141，21，19，876