2095. Delete the Middle Node of a Linked List ·

拜讀了你所不知道的 C 語言： linked list 和非連續記憶體一文中所提到的 “good taste” 段落 , 覺得非常有趣而躍躍欲試，所以找這題來練練手。（後來發現底下的例子也有寫到這題😅，而且效率又比我想到的解更好，甚至還有一些記憶體管理的細節，學到了！）

原始題目
#

這題是給定一個不固定長度 \(n\) 的鏈結串列，然後要求刪除最中間的那個節點（ node ）（精確來說是第 \(\lfloor \frac{n}{2} \rfloor\) 個節點）

值得紀錄之處
#

這裡所謂的 good taste 是指利用一些技巧，去減少「特例」發生的情形，進而使程式碼更加乾脆俐落。舉例來說，原本在這題常見的解法有兩種：

先用迴圈把整個鏈結串列遍歷，計算有幾個節點。算完再跑一次 for 迴圈把最中間的節點刪除。
利用 fast 和 slow 兩指標，丟進迴圈裡面， fast 每回合前進兩格， slow 每回合前進一格，這樣只要一次迴圈就可以抓到要刪除的節點並且刪除。
兩者的時間複雜度都是 \( \log (n)\), 但是後者的程式碼量會因為少一個迴圈而比較少，因此我以後者為比較標準。

非 indirect pointer 的解
#

此程式碼取自 leetcode 論壇的某位大大寫的詳解文章微調而得

class Solution {
public:
	ListNode* deleteMiddle(ListNode* head) {
		if (head -> next == nullptr)
			return nullptr;
		ListNode *slow = head, *fast = head -> next -> next;
		while (fast != nullptr && fast -> next != nullptr) {
			slow = slow -> next;
			fast = fast -> next -> next;
		}
		slow -> next = slow -> next -> next;
		return head;
	}
};

可以注意到，上面的解法 (line 4) 會有一個特例 (edge case), 如果開頭是 nullptr, 那就如何如何……。有時候特例一多，可能會寫了整面的 if-else, 看了就痛苦😵‍💫。如果有個魔法可以使這個特例更減少，那程式碼就可以更精簡，這也是我這次的練習目標。

因為題意規定 1 <= node.size() <= 100000, 因此前者的原本的做法：

不用判斷是否為空 list
要判斷是否只有一個 node, 若是只有一個 node, 則把該 node 刪除
若非只有一個 node, 則按照 fast, slow 做法從頭開始經過此 list 每個節點。
```
flowchart LR
	slow --> node_1
	subgraph node_1
	next_1
	end
	next_1 --> target
	subgraph target
	next_2
	end
	next_2 --> node_3
	subgraph node_3
	next_3
	end
```
如果我想操作 slow 指標來達成刪除的功能（暫不探討釋放記憶體的部分），就需要把被刪除的目標前一個 node 的 node->next 指向目標後一個 node 的 node->next, 所以最後 slow 會指向目標的上一個 node, 而 slow->next 才是要被刪除的節點。(前述程式碼 line 11)
另外根據題意可得，當 list 具有 1 個 node 跟 2~3 個 node 時，需要刪除的目標會不一樣 。
這會有個問題：我沒辦法巧妙的透過 initialize slow 跟 fast 兩個指標, 使得 edge case 被消滅。換言之，當 list 只有 1 個 node 的時候，我需要特別操作 head 而不是 slow, 才能把目標 node 刪除。 因此才有了下面 indirect pointer 的解法。

承上所述，我會需要某個「東西」，這個東西有辦法視情況具有 head 或 slow 的功能，而那個東西就是間接指標 (indirect pointer) ，一種指向指標的記憶體位址的指標（有點繞舌😆）。

原本 slow 無法對 head 造成影響

flowchart LR
	slow --> node_1
	head --> node_1
	subgraph node_1
	next_1
	end
	next_1 --> target
	subgraph target
	next_2
	end
	next_2 --> node_3
	subgraph node_3
	next_3
	end

使用 indirect_del 可以修改 head

刪除前

		flowchart LR
		indirect_del ==> head
		head --> target
		subgraph target
		next_1
		end
		next_1 --> node_2
		subgraph node_2
		next_2
		end
		next_2 --> node_3
		subgraph node_3
		next_3
		end

// 因為沒有 edge case, 所以跟後面刪除中間節點的程式碼可以一樣
*indirect_del = (*indirect_del)->next;

刪除後

	flowchart LR
		indirect_del ==> head
		head --> node_2
		subgraph target
		next_1
		end
		next_1 --> node_2
		subgraph node_2
		next_2
		end
		next_2 --> node_3
		subgraph node_3
		next_3
		end

使用 indirect_del 也可以刪除中間的任意節點

刪除前

	flowchart LR
		indirect_del ==> next_1
		head --> node_1
		subgraph node_1
		next_1
		end
		next_1 --> target
		subgraph target
		next_2
		end
		next_2 --> node_3
		subgraph node_3
		next_3
		end

*indirect_del = (*indirect_del)->next;

刪除後

	flowchart LR
		indirect_del ==> next_1
		head --> node_1
		subgraph node_1
		next_1
		end
		next_1 --> node_3
		subgraph target
		next_2
		end
		next_2 --> node_3
		subgraph node_3
		next_3
		end

indirect pointer 的解
#

(這個魔法我在原文花了好幾個小時反覆研究了很多遍，一開始覺得超級不好懂XD)

// good taste 的解法
class Solution {
public:
	ListNode* deleteMiddle(ListNode* head) {
		ListNode **indirect_del = &head, *fast = head;
		// 利用 go_next 去判斷 indirect_del 需不需要前進一格
		for(bool go_next = false; fast; fast = fast->next, go_next = !go_next)
			indirect_del = go_next ? &(*indirect_del)->next : indirect_del;
		*indirect_del = (*indirect_del)->next;
		return head;
	}
};

// 比較：多了 edge case 的解法
class Solution {
public:
	ListNode* deleteMiddle(ListNode* head) {
		if (head -> next == nullptr)
			return nullptr;
		ListNode *slow = head, *fast = head -> next -> next;
		while (fast != nullptr && fast -> next != nullptr) {
			slow = slow -> next;
			fast = fast -> next -> next;
		}
		slow -> next = slow -> next -> next;
		return head;
	}
};

因為多了這層「間接的關聯」， indirect_del 一開始是指向 head 的地址，因此可以快樂地除去前述惱人的 edge case. 之後 indirect_del 又可以指向任何一個 node 的 node->next 指標，以獲得所有指標的功能。到這邊可能要多對照幾次兩者之間有無 “indirect pointer” 的差別會比較容易理解，理解之後不禁感嘆程式這門藝術真是博大精深！

原始題目#

值得紀錄之處#

非 indirect pointer 的解#

indirect pointer 的解#

原始題目
#

值得紀錄之處
#

非 indirect pointer 的解
#

indirect pointer 的解
#