Linus: 這樣寫是不懂指針
你好，我是雨樂！
但凡刷過 leetcode 或者參加面試，大抵都遇到過如下這種問題：刪除單鏈表中 value 爲給定值的所有節點。
假設鏈表節點定義如下：
struct ListNode {
int value;
ListNode* next;
};那麼，爲了實現該功能，我們需要從頭到尾遍歷鏈表，同時刪除 value 等於給定值的節點，顯然，我們會像如下這樣寫：
void Remove(ListNode *head, int to_remove) {
ListNode *entry = head;
ListNode *prev = NULL;
while (entry) {
if (entry->val == to_remove) {
if (prev)
prev->next = entry->next;
else
head = entry->next;} else {
prev = entry; }
entry = entry->next;
}
}代碼實現中，我們所做的是遍歷列表，直到entry爲 NULL(第 5 行)。當我們遇到要刪除的節點時（第 6 行），我們將當前next指針的值分配給前一個，進而從當前鏈表中摘除當前元素（第 8 行）。
上述這種寫法，相對來說簡單、易理解，但 Linus Torvalds卻不這麼認爲，其曾經評價這種寫法：
At the opposite end of the spectrum, I actually wish more people understood the really core low-level kind of coding. Not big, complex stuff like the lockless name lookup, but simply good use of pointers-to-pointers etc. For example, I’ve seen too many people who delete a singly-linked list entry by keeping track of the “prev” entry, and then to delete the entry, doing something like
if (prev) prev->next = entry->next; else list_head = entry->next;
and whenever I see code like that, I just go “This person doesn’t understand pointers”. And it’s sadly quite common.
People who understand pointers just use a “pointer to the entry pointer”, and initialize that with the address of the list_head. And then as they traverse the list, they can remove the entry without using any conditionals, by just doing a “*pp = entry->next”
其大概意思就是，對於寫出本文一開始那種代碼的評價就是：*** 這個人不懂指針 (This person doesn’t understand pointers)***。
那麼，Linus 推薦的寫法又是什麼樣的呢？
void Remove(ListNode *head, int to_remove) {
ListNode **pp = &head;
ListNode *entry = head;
while (entry) {
if (entry->val == to_remove)
*pp = entry->next;
else
pp = &entry->next;
entry = entry->next;
}
}這塊代碼看起來相對簡潔，但是，如果第一次遇到這種實現，可能需要花一點時間進行理解~~
實際上刷過題的都知道，list 相關問題首先在棧上聲明一個dummy node，能簡化各種插入刪除操作代碼。使用dummy node操作後，代碼如下：
void Remove(ListNode *head, int to_remove) {
ListNode tmp;
tmp.next = head;
ListNode *pre = tmp;
while (pre->next) {
if (pre->next->val == to_remove) {
pre->next = pre->next->next;
} else {
pre = pre->next;
}
}
}相比來說，較 Linus 的實現方式更爲簡潔，但明顯的，需要生成一個 dummy 節點，最明顯的，內存使用上並不是最優，儘管其更易於理解和實現。
鏈表屬於 LC 中相對來說比較簡單的部分，選擇一種適合自己的方式，並不一定非要選擇最優，選擇一個適合自己的。至於 Linus 實現的這種，可以保留意見，且當其最優吧，畢竟：沒有人比Linus更懂指針，哈哈哈~
你好，我是雨樂，從業十二年有餘，歷經過傳統行業網絡研發、互聯網推薦引擎研發，目前在廣告行業從業 8 年。目前任職某互聯網公司高級技術專家一職，負責廣告引擎的架構和研發。
本公衆號專注於架構、技術、線上 bug 分析等乾貨，歡迎關注。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/gS5I4LmlFTUsOf3l2ju8Bg