受到 你所不知道的 C 語言: linked list 和非連續記憶體 的啟發，記錄對於 Indirect Pointer 的學習歷程，並嘗試使用 Rust 實現此概念。
測試程式碼: https://github.com/hank20010209/good-taste-linked-list
首先定義 Linked List 資料結構，定義節點本身以及 Linked List 本身
吳他，惟手熟爾
typedef struct Node {
int value;
struct Node *next;
}Node;
typedef struct List {
Node *head;
}List;
To init the Linked List
List *init_list()
{
List *l = (List *)malloc(sizeof(List));
l->head = NULL;
return l;
}
初始化 Linked List，並將初始化完成的 Linked List 回傳
Find Node in Linked List
Return the pointer point to Node if in Linked List
Return NULL pointer if not in Linked List
Node *find_node(List *list, int target)
{
Node *temp = list->head;
while(temp && temp->value != target) {
temp = temp->next;
}
return temp;
}
insert Node to the tail of Linked List
void insert_tail(List *list, int value)
{
Node *curr = list->head;
Node *prev = NULL;
Node* new = (Node *)malloc(sizeof(Node));
new->next = NULL;
new->value = value;
while(curr) {
prev = curr;
curr = curr->next;
}
if(!prev)
list->head = new;
else
prev->next = new;
}
在 Linked List 的尾端插入節點，使用 prev 和 curr 去走訪節點，prev 為 NULL 的情況，表示 Linked List 沒有任何節點或是為 NULL，否則就向 prev->next 插入節點，圖像化如下
在 prev 不為 NULL，也就是 Linked List 不為空的情況下，存在節點的情況下
在 prev 為 NULL，也就是 Linked List 為空，沒有節點的情況下
Remove the Node in Linked List
If target not in Linked List, return
void remove_node(List *list, Node *target)
{
if(!target) return;
Node *prev = NULL;
Node *curr = list->head;
while(curr != target) {
prev = curr;
curr = curr->next;
}
if(!prev)
list->head = target->next;
else
prev->next = target->next;
}
使用 prev 以及 curr 走訪 Linked List 找到目標節點，接下來分成兩種情況進行討論，分別為刪除的為頭節點或是其他節點
刪除其他節點的情況
刪除頭節點的情況
可以發現到在 remove_node 以及 insert_tail 都會出現特定情況需要進行處理，通過 if-else 判斷是否為頭節點，而以下將使用間接指標 (或稱為指標的指標) 對程式碼進行優化，除去對於特例的判斷
前面 remove_node 的想法為將節點 Node 的記憶體地址儲存到 curr 和 prev 中，通過 curr 和 prev 走訪 Linked List，找到 target 時便停止。
而 Indirect Pointer 的想法為運用指向到節點記憶體地址的指標進行操作，原先的 curr 和 prev 中儲存的是節點本身的記憶體地址，反參考 curr 和 prev 我們能夠得到節點本身，而 Indirect Pointer 中儲存的是指向到節點記憶體地址的指標，如果我們對其進行反參考，我們會得到的是該節點的記憶體地址，概念說明如下
#include <stdio.h>
#include <stdlib.h>
void foo(int *a_ptr)
{
a_ptr = NULL;
}
int main(void)
{
int a = 3;
int *a_ptr = &a;
printf("%d\n", *a_ptr);
foo(a_ptr);
printf("%d\n", *a_ptr);
}
上面這一段程式碼，我們有一個指向到整數的指標變數 a_ptr，接著我們將指標變數傳入 foo() 函式，讓 a_ptr 由原先的指向變數 a 變為指向到 NULL。
我們可以通過第 15 行查看對 a_ptr 的修改是否成功，如果修改成功，則第 15 行會出現對空指標進行反參考的錯誤，造成記憶體區段錯誤。
以下為執行結果
3
3
可以發現我們並沒有成功修改 a_ptr 所指向的物件，原因為 C 語言的函式傳遞是以傳值進行的，傳入函式的參數會產生一份複本到函式中，而我們在函式中修改的參數，實際上修改的是剛剛產生的複本。舉一個簡單的例子
#include <stdio.h>
#include <stdlib.h>
void foo(int a)
{
a = 10;
}
int main(void)
{
int a = 3;
printf("%d\n", a);
foo(a);
printf("%d\n", a);
}
上面這個例子十分容易理解，我們在 foo() 中修改的 a，實際上是在函式中產生的複本，不會影響到 main 中的 a。
如果要針對 a 進行修改，我們需要傳入指向到 a 的指標變數，修改 a 記憶體地址中儲存的資料，範例如下
#include <stdio.h>
#include <stdlib.h>
void foo(int *a)
{
*a = 10;
}
int main(void)
{
int a = 3;
printf("%d\n", a);
foo(&a);
printf("%d\n", a);
}
圖解如下
這裡可以注意到，對於 call by value，如果我們修改傳入函式中的值，實際上我們是修改到他的複本，但是我們可以修改他背後的資料，以 *a 而言，指標變數中儲存的是記憶體地址，而我們對其反參考可以得到記憶體地址儲存的資料，對於 call by value，我們無法修改變數中儲存的值，也就是我們無法修改指標中儲存的記憶體地址，但是我們可以通過反參考指標修改背後的資料。
對應到上面的範例，我們是傳入指標變數到 foo() 中，在 foo() 中我們得到 *a 的複本，稱為 copy *a，之後我們反參考 copy *a，修改記憶體地址指向的資料。
接著回到我們在一開始看到的例子
#include <stdio.h>
#include <stdlib.h>
void foo(int *a_ptr)
{
a_ptr = NULL;
}
int main(void)
{
int a = 3;
int *a_ptr = &a;
printf("%d\n", *a_ptr);
foo(a_ptr);
printf("%d\n", *a_ptr);
}
這裡我們嘗試修改變數的值，也就是修改指標變數儲存的記憶體地址，將其修改為 NULL，我們修改到的是變數複製出來的複本，而不是在 main() 中 a_ptr 本身，因此在第 15 行不會發生反參考空指標所導致的記憶體區段錯誤。
這裡整理一下，如果我們要對 a 進行修改，我們需要傳入 *a。而如果我們要修改 *a，我們會想到我們可能要傳入 **a，*a 為指標，而 **a 稱為指標的指標，又稱為間接指標。我們可以通過間接指標去修改指標變數中儲存的值，只需要反參考間接指標，修改其值即可，以下範例
#include <stdio.h>
#include <stdlib.h>
void foo(int **a_ptr)
{
*a_ptr = NULL;
}
int main(void)
{
int a = 3;
int *a_ptr = &a;
printf("%d\n", *a_ptr);
foo(&a_ptr);
printf("%d\n", *a_ptr);
}
output:
3
Segmentation fault (core dumped)
從以上範例可以看到，我們通過間接指標，去修改指標內儲存的值。
而接下來我們將使用間接指標的手法，對 Linked List 的實作進行優化。
前面 remove_node 的想法為我們使用一個指標變數，儲存該節點的記憶體地址，反參考後就可以得到節點本身。
而這邊使用間接指標的想法，我們儲存的指標，是指向到該節點的記憶體地址，如果我們反參考指標，得到的是節點的記憶體地址。
以下為實作部分
void remove_list_node(List *list, Node *target)
{
Node **indirect = &list->head;
while (*indirect != target)
indirect = &(*indirect)->next;
*indirect = target->next;
}
我們使用指向到 Node 指標的指標變數 indirect，裡面儲存指向到 list->head 的指標，也就是說 indirect 是一個指標的指標，也稱為間接指標，indirect is a pointer to pointer, which mean a pointer to your pointer value，your pointer value point to Node, so the type of pointer value is Node *, and the type of the pointer to your pointer value is Node **.
之後我們開始通過 indirect 去走訪 Linked List，*indirect 這邊為對 indirect 進行反參考，得到的會是節點的記憶體地址，型別為 Node *，通過節點的記憶體地址和 target 進行比較，target 同樣也是記憶體地址，意義為節點的記憶體地址。
第 6 行，首先我們對 indirect 進行反參考，得到 Node *，也就是 Node 的記憶體地址，通過箭頭運算子取得成員 next，成員 next 指向到下一個節點，型別為 Node *，意義為指向到節點的記憶體地址，接著我們對他進行取址，得到 Node **，意義為指向到指向到節點的記憶體地址，這邊聽起來有些繞口，概念上就是儲存的是指向到節點的記憶體地址。
舉一個簡單的例子
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int a;
int b;
}Node;
int main(void)
{
Node a = {.a = 1, .b = 2};
Node *a_ptr = &a;
Node **a_ptr_ptr = &a_ptr;
printf("%d", (*a_ptr_ptr)->a);
}
圖解為以下
指標變數本身也是一個變數，有自己的記憶體地址，只是該變數裡面儲存的值為記憶體地址
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int a;
int b;
}Node;
int main(void)
{
Node a = {.a = 1, .b = 2};
Node *a_ptr = &a;
Node **a_ptr_ptr = &a_ptr;
printf("Address of Node a: %-10x\n\n", &(a));
printf("Context of a_ptr: %-10x\n", a_ptr);
printf("Dereference of a_ptr: %-10x\n", *a_ptr);
printf("Address of a_ptr: %-10x\n\n", &(a_ptr));
printf("Context of a_ptr_ptr: %-10x\n", a_ptr_ptr);
printf("Dereference of a_ptr_ptr: %-10x\n", *a_ptr_ptr);
printf("Address of a_ptr_ptr: %-10x\n", &(a_ptr_ptr));
}
output
Address of Node a: 61ff18
Context of a_ptr: 61ff18
Dereference of a_ptr: 1
Address of a_ptr: 61ff14
Context of a_ptr_ptr: 61ff14
Dereference of a_ptr_ptr: 61ff18
Address of a_ptr_ptr: 61ff10
Node a 的記憶體地址為 0x61ff18。
Node *a_ptr 為指標變數，記憶體地址為 0x61ff14，內容為 0x61ff18，為一個指向到 Node 的指標，對 a_ptr 進行反參考，意味著存取 a_ptr 指標變數內容所指向的資料，也就是 0x61ff18 所指向的資料，存取到 Node a 的第一個成員，得到 1。
Node **a_ptr_ptr 為指標變數，記憶體地址為 0x61ff10，內容為 0x61ff14，為一個指向到 Node * 的指標，對 a_ptr_ptr 進行反參考，意味著存取 a_ptr_ptr 指標變數內容所指向的資料，也就是 0x61ff14 所指向的資料，0x61ff14 中的資料為 0x61ff18。
將這個概念應用在 remove_list_node 中，圖解如下
這是初始情況，indirect 為一個指標的指標，也就是 indirect 為一個指標變數，儲存指向到節點的指標。(加上記憶體地址方便理解)
不同於原先的實作，指向到節點本身，這邊是儲存指向到節點的指標，概念上為儲存要更新的位置，而不是要更新的節點本身。反參考 indirect 得到的是指向到節點的記憶體地址。
接著看到走訪，假設目前情況如下
首先先對 indirect 進行反參考，會得到節點的下一個節點的指標，概念上為接下來我們要更新的地址
接著我們通過箭頭運算子存取成員 next，也就是 (*indirect)->next
接著我們取出指向到下一個節點的指標，也就是取出指向 Node * 的指標&(*indirect)->next，型別為 Node **
:::info
由走訪節點的過程中我們可以觀察到一件事情，indirect 所維護的，是我們要更新的位置，我們接下來要更新的位置是儲存在 next 中的，型別為 Node *，而我們要存取要更新的位置，因此需要使用 Node ** 進行操作。
在上面的實作中，我們可以通過 *indirect 來得到 Node *，進而去存取下一個節點的資訊。
:::
如果 *indirect 就是我們要刪除的節點，也就是 *indirect == target，則圖解為以下
我們可以通過 *indirect 得到要刪除的節點本身，也就是 target，型別為 Node *，目前 *indirect 的內容為前一個節點指向的下一個節點，於是，我們可以直接通過修改 *indirect 去改變前一個節點所指向的下一個節點，概念上可以理解為修改前一個節點中，next 的內容。
*indirect = target->next 的意義為將前一個節點的下一個節點改變為 target 的下一個節點。
這時候的 *indirect 為以下
可以注意到，實際上 target 並沒有被我們移除。
在最一開始的 while 迴圈判斷時，會先判斷 *indirect != target，而我們最一開始條件便不成立了，因此不會進入到 while 迴圈，目前圖解如下
接著我們通過 *indirect 獲得第一個節點本身，型別為 Node *，第一個節點本身也就是 list_head，接著我們將 *indirect 設為頭節點的下一個節點，也就是將 *indirect 設為 target->next，圖解如下
我們在最一開始直覺上的實作，是使用 direct pointer 的方式，直接針對節點本身進行操作，但是會有一些例外狀況需要處理，如頭節點為特殊情況。
而 indirect pointer 的想法為我們針對接下來要更新的位置進行判斷，好處是不會有例外情況進行處理，因為我們並沒有直接針對頭節點進行操作。
給定兩個已經完成排序的單向鏈結串列，請將這兩個鏈結串列進行合併，並回傳合併完成的鏈結串列頭節點。
直覺上的做法，是建立一個頭節點，接著我們開始走訪 list1 和 list2，將 val 較小的節點串到我們建立的節點上，完成後回傳我們建立頭節點的下一個節點 (我們建立的頭節點概念上是一個 dummy node)
以下為該實作程式碼
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode *ptr = head;
while(list1 && list2) {
if(list1->val < list2->val) {
ptr->next = list1;
list1 = list1->next;
}
else {
ptr->next = list2;
list2 = list2->next;
}
ptr = ptr->next;
}
ptr->next = list1 ? list1 : list2;
return head->next;
}
這裡我們的 head 使用 malloc 配置了一塊記憶體空間，而我們可以使用間接指標的方法優化這一段空間，讓我們不用使用 malloc 去對 head 進行記憶體空間的分配
前面的想法為 head 為一個實際存在的節點，而我們通過 ptr 去維護 head 後面串接的節點，但實際上 head 為一個 dummy node，內容沒有意義，只是為了讓我們串接後面的節點。
這邊使用間接指標的想法，概念上是改變 head 所指向的節點，直接修改 head 的內容，我們直接宣告一個 head pointer，指向到節點，並初始化為 NULL，之後我們使用 **ptr = &head，ptr 裡面儲存的，是 head 這個指標變數本身的指標，反參考 ptr 會得到 head 指標變數所在的記憶體地址。
我們可以直接通過 *ptr = some address 直接改變 head 的內容，也就是 head 所儲存的指向到節點的記憶體地址。
接著我們可以通過 &(*ptr)->next 得到指向 head 下一個節點的指標的指標。
以下為初始情況
加入第一個節點 (直接修改 head 的內容，也就是讓 head 直接指向某一個節點)，(*ptr) = list?
通過 (*ptr) 存取到節點本身的指標，通過箭頭運算子存取成員
這裡的概念如同前面提及的 remove_node 一樣，我們是維護記憶體地址本身，而非節點本身。
實作如下
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode *head;
struct ListNode **ptr = &head;
while(list1 && list2) {
if(list1->val < list2->val) {
*ptr = list1;
list1 = list1->next;
}
else {
*ptr = list2;
list2 = list2->next;
}
ptr = &(*ptr)->next;
}
(*ptr) = list1 ? list1 : list2;
return head;
}
接著觀察到 if-else 的部分，發現要做的操作都是反參考 ptr，指向到下一個要接上的節點，接著更新到下一個節點，我們可以使用一個指標變數去指向 L1 或是 L2。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode *head;
struct ListNode **ptr = &head;
struct ListNode **node;
while(list1 && list2) {
node = (list1->val < list2->val) ? (&list1) : (&list2);
*ptr = *node;
ptr = &(*ptr)->next;
*node = (*node)->next;
}
(*ptr) = list1 ? list1 : list2;
return head;
}
使用 for 迴圈可以減少一些行數
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode *head = NULL, **ptr = &head, **node = NULL;
for(; list1 && list2; *node = (*node)->next, ptr = &(*ptr)->next) {
node = (list1->val < list2->val) ? (&list1) : (&list2);
*ptr = *node;
}
(*ptr) = list1 ? list1 : list2;
return head;
}
雖然可以將操作寫入 for 迴圈中，但程式碼將不易閱讀
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode *head = NULL, **ptr = &head, **node = NULL;
for(; list1 && list2; node = (list1->val < list2->val) ? (&list1) : (&list2), *ptr = *node, *node = (*node)->next, ptr = &(*ptr)->next);
return (*ptr) = list1 ? list1 : list2, head;
}
給定一單向鏈結串列，刪除中間的節點後回傳
直覺做法
struct ListNode* deleteMiddle(struct ListNode* head){
struct ListNode* slow_prev;
struct ListNode* slow = head;
struct ListNode* fast = head;
if(!head->next) return NULL;
while(fast && fast->next){
slow_prev = slow;
slow = slow->next;
fast = fast->next->next;
}
slow_prev->next = slow->next;
return head;
}
我們可以嘗試使用間接指標，上面的作法次我們使用一個指標去指向到節點，如果對該指標進行反參考，我們會得到節點本身，而使用間接指標，我們要操作的對象是針對節點中 next 這個成員，要修改 next，我們需要使用 Node ** (指向到 next) 來對 next 進行操作，也就是間接指標，以下範例
struct ListNode* deleteMiddle(struct ListNode* head){
struct ListNode **indirect = &head;
for(struct ListNode *fast = head; fast && fast->next; fast = fast->next->next)
indirect = &(*indirect)->next;
*indirect = (*indirect)->next;
return head;
}
這邊走訪時概念和上方刪除節點的概念相同，都是針對接下來要操作的位置進行操作。
這邊同樣可以發現，實際上我們沒有將節點移除，這邊我們嘗試將節點占用的記憶進行釋放。
我們需要維護一個指標，指向到 *indirect 的前一個節點
struct ListNode* deleteMiddle(struct ListNode* head){
struct ListNode **indirect = &head;
struct ListNode *prev = NULL;
for(struct ListNode *fast = head; fast && fast->next; fast = fast->next->next) {
prev = *indirect;
indirect = &(*indirect)->next;
}
prev->next = (*indirect)->next;
free(*indirect);
return head;
}
反參考 indirect 得到的是下一個節點，而在 indirect 更新之前，我們先使用一個指標儲存 indirect，達到儲存前一個節點的目標。
迴圈結束後，*indirect 為中間節點，因此只要我們將 prev->next = (*indirect)->next 便完成移除中間節點的操作了，之後我們再將 *indirect 使用 free() 進行釋放便完成操作，以給定單向鏈結串列 [1,3,4,7,1,2,6] 為例，在迴圈走訪結束後，prev 指向節點的值為 4，*indirect 指向節點的值為 7。
接著我們把 prev 的下一個節點設為 *indirect 的下一個節點，這邊其實 prev->next = (*indirect)->next 的意義等同於 (*indirect) = (*indirect)->next，相當於把指向到 7 的節點設為指向到 1 的節點，也就是，這邊 *indirect 的內容為 1
接著我們會將 *indirect 進行釋放，可以發現到我們將指向到 1 的節點進行釋放了，這會導致我們在後續走訪的時候存取到空指標。
我們試著執行後，會發現 leetcode 中的 AddressSanitizer 會發出 heap-use-after-free 的錯誤。
要解決這個問題，我們可以使用一個指標去存放 (*indirect)->next，實作如下
struct ListNode* deleteMiddle(struct ListNode* head){
struct ListNode **indirect = &head;
struct ListNode *prev = NULL;
if(!head->next) return NULL;
for(struct ListNode *fast = head; fast && fast->next; fast = fast->next->next) {
prev = *indirect;
indirect = &(*indirect)->next;
}
struct ListNode *next = (*indirect)->next;
free(*indirect);
prev->next = next;
return head;
}
圖解如下，首先是 *next = (*indirect)->next 的概念如下
這邊沒有直接讓 next 畫在 *indirect 節點的 next 下方，是為了不和 Node ** 混淆。
接著 prev->next = next
如此我們便完成了釋放中間節點的操作。
也可以使用以下作法
struct ListNode* deleteMiddle(struct ListNode* head){
struct ListNode **indirect = &head;
struct ListNode *prev = NULL;
if(!head->next) return NULL;
for(struct ListNode *fast = head; fast && fast->next; fast = fast->next->next) {
prev = *indirect;
indirect = &(*indirect)->next;
}
struct ListNode *del = (*indirect);
prev->next = (*indirect)->next;
free(del);
return head;
}
在 Rust 版本中如果我們想要使用快慢指標，則會發現到一些問題，最一開始 slow 和 fast 都需要指向到 head，接著 slow 和 fast 都需要走訪 Linked List，因此 slow 和 fast 都需要是可變的。
impl Solution {
pub fn delete_middle(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
}
}
delete_middle 函式傳入了一個 Option<Box<ListNode>>，Option 如同其他的 enum 型別，我們可以使用 match 去匹配其所有的結果，在 Linked List 的實作中，會有空節點的情況發生，也就是 nullptr，但是在 rust 中並沒有 nullptr 存在，而是通過 Option，在 Option 中有兩個成員，一個為 None，另外一個為 Some(val)，我們可以使用 match 對 Option 進行解構，或是使用更加簡單的方式，使用 ? 進行解構，以下舉例
struct Person {
job: Option<Job>,
}
#[derive(Clone, Copy)]
struct Job {
phone_number: Option<PhoneNumber>,
}
#[derive(Clone, Copy)]
struct PhoneNumber {
area_code: Option<u8>,
number: u32,
}
impl Person {
fn work_phone_area_code(&self) -> Option<u8> {
match self.job {
Some(job) => {
match job.phonstruct Person {
job: Option<Job>,
}
#[derive(Clone, Copy)]
struct Job {
phone_number: Option<PhoneNumber>,
}
#[derive(Clone, Copy)]
struct PhoneNumber {
area_code: Option<u8>,
number: u32,
}
impl Person {
fn work_phone_area_code(&self) -> Option<u8> {
match self.job {
Some(job) => {
match job.phone_number {
Some(phone_number) =>
match phone_number.area_code {
Some(area_code) => Some(area_code),
number => number,
None => None,
},
None => None,
}
}
None => None,
}
}
}
fn main() {
let p = Person {
job: Some(Job {
phone_number: Some(PhoneNumber {
area_code: Some(61),
number: 439222222,
}),
}),
};
println!("{}", p.work_phone_area_code().unwrap());
}
可以看到 work_phone_area_code 的部分，如果使用 match 進行解構，將會看起來十分的雜亂，這邊可以使用 ? 對 Option 進行解構
impl Person {
fn work_phone_area_code(&self) -> Option<u8> {
self.job?.phone_number?.area_code
}
}
x? 為表達式，能夠對他進行取值，self.job?phone_number 意義為對 Option<job> 取值，當 job 為 Some(value) 時，取出 phone_number。
回到題目本身，我們需要 slow 和 fast 對 Linked List 進行走訪，slow 需要為 head 的可變引用，因為我們需要修改他所指向的下一個節點，而 fast 只是用來走訪 Linked List 的，因此只需要不可變引用即可，實作如下
impl Solution {
pub fn delete_middle(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut slow = &mut head;
let mut fast = &head;
}
}
但上面這個寫法有一個問題，我們無法同時持有對於某一個物件的可變引用以及不可變引用，為此，我們需要再創造一個新的物件 head，他的內容需要和 head 相同，但是是兩個獨立的物件
impl Solution {
pub fn delete_middle(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut slow = &mut head;
let mut fast = &(head.clone());
}
}
概念如下
#[derive(Clone)]
struct Obj {
a:i32
}
fn main() {
let mut a: Obj = Obj {
a: 1,
};
let mut b = &a;
let mut c = &(a.clone());
println!("{:p}", &a);
println!("{:p}", b);
println!("{:p}", c);
}
output
0x7ffe4eb9ed58
0x7ffe4eb9ed58
0x7ffe4eb9ed5c
可以看到 a 和 c 是不同的物件，如此我們便可以利用 fast 以及 slow 對 Linked List 完成走訪了
impl Solution {
pub fn delete_middle(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut fast = &(head.clone());
let mut slow = &mut head;
while fast.is_some() && fast.as_ref()?.next.is_some() {
slow = &mut (slow.as_mut()?.next);
fast = &(fast.as_ref()?.next.as_ref()?.next);
}
*slow = (*slow).as_mut()?.next.take();
head
}
}
source
同樣的，我們也可以使用 indirect pointer 的概念進行操作
impl Solution {
pub fn delete_middle(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut fast = &(head.clone());
let mut indirect = &mut head;
while fast.is_some() && fast.as_ref()?.next.is_some() {
fast = &(fast.as_ref()?.next.as_ref()?.next);
indirect = &mut indirect.as_mut().unwrap().next;
}
*indirect = indirect.as_mut().unwrap().next.take();
head
}
}
你所不知道的 C 語言: linked list 和非連續記憶體
Rust. Fast&Slow pointers Solution
iThome鐵人賽
看影片追技術