# 2020q3 Homework1 (quiz 1)
contributed by <`willyouyang`>
## Table of content
[TOC]
## 先備知識
- 題目: [第一週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)
- 參考資料: [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list?type=view)
- 使用的資料結構是 `單向的鏈結串列(singly linked list)`，如以下表示:
```clike
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= "node_name1|{<value>value1|<ref>&next}"]
node2 [label= "node_name2|{<value>value2|<ref>NULL}"]
NULL[shape=plaintext]
node1:ref -> node2
node2:ref -> NULL
}
```
- 再來是對這個單向鏈結串列所做的一系列操作，如以下的程式碼:
```clike=
int main(int argc, char const *argv[])
{
node_t *head = NULL;
print_list(head);
add_entry(&head, 72);
add_entry(&head, 101);
add_entry(&head, 108);
add_entry(&head, 109);
add_entry(&head, 110);
add_entry(&head, 111);
print_list(head);
node_t *entry = find_entry(head, 101);
remove_entry(&head, entry);
entry = find_entry(head, 111);
remove_entry(&head, entry);
print_list(head);
/* swap pair.
* See https://leetcode.com/problems/swap-nodes-in-pairs/
*/
head = swap_pair(head);
print_list(head);
head = reverse(head);
print_list(head);
return 0;
}
```
`第3行`宣告鏈結串列的`頭指標(head)`，初始是指向NULL，沒有內容，如以下圖所示
`第7到12行`將`多個節點(node_t)`加入串列
`第16到20行`則將數值為`101`和`111`的節點分別刪除
`第27行`做兩兩相鄰節點的交換
`第30行`則進行串列的反轉
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
head[shape=plaintext,fontcolor=red]
NULL[shape=plaintext]
head -> NULL
}
```
## add_entry
```clike=
void add_entry(node_t **head, int new_value)
{
node_t **indirect = head;
node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
AA1;
while (*indirect)
indirect = &(*indirect)->next;
AA2;
}
```
AA1 和 AA2 都有兩個選項，分別是 `assert(new_node)` , `*indirect = new_node`
`第10到12行` 根據 [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list?type=view) 裡面提到的 `指標的指標(pointer to pointer)` 的操作，`AA2` 應該選 `*indirect = new_node` ，`AA1` 則是`assert(new_node)` ，檢查新生成的 new_node 是不是在合法的記憶體區段，節點加入串列的過程如下:
- `add_entry(&head, 72)` : 插入值為72的節點，透過 `指標的指標 indirect` 紀錄 `指標 head` 所在的記憶體位置(第3行) ，因為此時檢驗出串列還沒有放東西(head 為 NULL)(第10行)，直接將新建立的節點 `new_node` 放進 `指標 head` 所指向的位置(第12行)(* 表示取值的動作，所以 `*indirect` 等同 head)
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
new_node [label= " new_node |{ <value> 72 | <next> NULL}"]
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
indirect -> head
head -> NULL
new_node -> NULL
}
```
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
new_node [label= " new_node |{ <value> 72 | <next> NULL}"]
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
indirect -> head
head -> new_node
new_node:next-> NULL
}
```
- `add_entry(&head, 101)` : 假設新建立的節點為 new_node2 ，`指標的指標 indirect` 從指標 head 開始走訪，還沒有檢測到空的指標，所以在`第11行`以 `*indirect` 存取 指標的指標現在所指向的節點，然後存取這個節點的 next`(*indirect->next)`，最後將 next 所在的位址存回 indirect `(&(*indirect->next))` ，如以下圖示:
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
new_node [label= " new_node |{ <value> 72 | <next> NULL}"]
new_node2 [label= " new_node2 |{ <value> 101 | <next> NULL}"]
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
indirect -> new_node:next
head -> new_node
new_node:next-> NULL
new_node2 -> NULL
}
```
- 根據上圖，在第10行檢測到空指標，接者跳出迴圈，在第12行以 `*indirect` 存取 `new_node->next`，將 `new_node2` 指派到 `*indirect` ，以達到修改 new_node 下一個指向節點的目的:
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
new_node [label= " new_node |{ <value> 72 | <next> &new_node2}"]
new_node2 [label= " new_node2 |{ <value> 101 | <next> NULL}"]
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
indirect -> new_node:next -> new_node2
head -> new_node
new_node2:next-> NULL
}
```
## find_entry
```clike=
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next)
/* interate */;
return current;
}
```
`第3行`用指標 current 指向鏈結串列的頭(head)
`第4行`一個迴圈，從 head 開始走訪，以 `current->value` 檢驗是不是我們想要找到的值，如果是就跳出迴圈
`第6行`回傳找到的目標節點
下圖描述回傳值為 101 的節點的過程: `find_entry(&head, 101)`
- 指標 current 指向 `head` ，即指向 `node1`
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> &node2}"]
node2 [label= " node2 |{ <value> 101 | <next> &node3}"]
node3 [label= " node3 |{ <value> 108 | <next> &node4}"]
node4 [label= " node4 |{ <value> 109 | <next> NULL}"]
head[shape=plaintext,fontcolor=red]
current[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
head -> node1
current -> node1
node1:next -> node2
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
- 透過 `current->value` 驗證是不是數值 101 ，不是就讓 `current` 指向下一個節點 `node2`
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> &node2}"]
node2 [label= " node2 |{ <value> 101 | <next> &node3}"]
node3 [label= " node3 |{ <value> 108 | <next> &node4}"]
node4 [label= " node4 |{ <value> 109 | <next> NULL}"]
head[shape=plaintext,fontcolor=red]
current[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
head -> node1
current -> node2
node1:next -> node2
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
- 此時透過第4行迴圈的條件，找到值為101的節點，回傳 `current(node2)`
## remove_entry
```clike=
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
如同 `add_entry` 透過指標的指標走訪整個 list，此時`*indirect` 紀錄的是`當下的節點指標`，同時也是`上一個節點內紀錄的 next 指標`，所以在`第8行`將當下指標的下一個節點拿來更新`前一個指標紀錄的 next 指標`，就能達到刪除節點的目的，最後在`第9行`把刪除節點的記憶體釋放，流程如下:
- 假設執行 `remove_entry(&head,101)` ，即刪除值為101的節點，此時透過指標的指標 `indirect` 指到刪除的節點(即 `node1->next` 或 `node2`):
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> &node2}"]
node2 [label= " node2 |{ <value> 101 | <next> &node3}"]
node3 [label= " node3 |{ <value> 108 | <next> &node4}"]
node4 [label= " node4 |{ <value> 109 | <next> NULL}"]
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
head -> node1
indirect ->node1:next
node1:next -> node2
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
- `第8行`的指令會用 node3 的指標更新 node1 指標的 next ，即 `node1->next = node3`:
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> &node3}"]
node2 [label= " node2 |{ <value> 101 | <next> &node3}"]
node3 [label= " node3 |{ <value> 108 | <next> &node4}"]
node4 [label= " node4 |{ <value> 109 | <next> NULL}"]
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
head -> node1
indirect ->node1:next
node1:next -> node3
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
- 最後在第9行釋放刪除節點 node2 的記憶體，得到最後的 list:
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> &node3}"]
node3 [label= " node3 |{ <value> 108 | <next> &node4}"]
node4 [label= " node4 |{ <value> 109 | <next> NULL}"]
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
head -> node1
indirect ->node1:next
node1:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
## swap_pair
```clike=
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; BB1) {
node_t *tmp = *node;
BB2;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
swap_pair 函式會將串列裡兩兩相鄰的節點進行交換，例如: `1 -> 2 -> 3 -> 4` 會變成 `2 -> 1 -> 4 -> 3` ，所以在`第3行`裡迴圈進行的每一步走訪應為兩個節點，這是我們要填進 `BB1` 的答案，選項有:
```
(a) node = (*node)->next->next
(b) *node = (*node)->next->next
(c) *node = ((*node)->next)->next
(d) *node = &((*node)->next)->next
(e) node = &(*node)->next->next
(f) *node = &(*node)->next->next
```
- 在`第3行` node 為`指標的指標( pointer to pointer)`用來作為走訪這個串列的 iterator，假設串列以下圖所示，且指標 head 指向 node1:
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> &node2}"]
node2 [label= " node2 |{ <value> 109 | <next> &node3}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
head[shape=plaintext,fontcolor=red]
NULL[shape=plaintext]
head -> node1
node1:next -> node2
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
- 上圖使用 `print_list` 函式會印出 `72 -> 109 -> 110 -> 111` 的順序，我們使用指標的指標 node 指向 node1 ，並使用 `(b)`的答案走訪這個 list ，如以下的程式碼驗證:
```clike
node_t ** node = &head;
*node = (*node)->next->next;
print_list(head);
```
- 輸出的結果為 `110 -> 111`，如以下的圖所示，這個結果說明使用 `*node` 作為走訪 `list` 的 `iterator`，會更改到裡面各個節點的內容，所以選項 `b,c,d,f` 應該剔除
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
head[shape=plaintext,fontcolor=red]
NULL[shape=plaintext]
head -> node3
node3:next -> node4
node4:next -> NULL
}
```
- 剩下 `a,e` 的選項，由於 node 紀錄的是它所指向指標的地址，應該使用 & 運算子對 當前指標的後兩個指標作取址的動作，所以答案為 `e`
`第5到7行`用於指標的 swap 交換，這是選擇 `BB2` 答案的線索，`BB2` 的選項如下:
```
(a) node = (*node)->next
(b) node = &(*node)->next
(c) *node = (*node)->next
(d) *node = &(*node)->next
(e) *node = &((*node)->next)
```
- 第4行使用指標 temp 保存`指標的指標 node` 目前指向的指標，代表下一行將會改變 node 指向指標的內容，而不是改變 node 指向的對象，所以 `a,b` 予以剔除，又由於 `*node` 指的是某個節點，不是指標的位址，不需要使用到 `&` 運算子，最後的答案是 `c` ，完整最終的程式碼如下:
```clike=
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) {
node_t *tmp = *node;
*node = (*node)->next;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
假設我們交換以下串列的前2個節點 `node1` 和 `node2` ，透過 `*node`(以 `node_t` 表示)指向 `node1`:
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> &node2}"]
node2 [label= " node2 |{ <value> 109 | <next> &node3}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
node_t[shape=plaintext,fontcolor=green]
head[shape=plaintext,fontcolor=red]
NULL[shape=plaintext]
node_t -> node1
head -> node1
node1:next -> node2
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
- `node_t *tmp = *node`: 使用 tmp 記住 node1 節點，以利後面的交換機制
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> &node2}"]
node2 [label= " node2 |{ <value> 109 | <next> &node3}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
node_t[shape=plaintext,fontcolor=green]
tmp[shape=plaintext,fontcolor=blue]
head[shape=plaintext,fontcolor=red]
NULL[shape=plaintext]
node_t -> node1
tmp -> node1
head -> node1
node1:next -> node2
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
- `*node = (*node)->next`: 將 `node` 指向 `node1` 的下一個節點 `node2` ，由於 `*node` 同時也代表了 `head` 指標，`head` 也跟著指向了 `node2` ，此時串列的頭指標被 `node2` 取代:
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> &node2}"]
node2 [label= " node2 |{ <value> 109 | <next> &node3}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
node_t[shape=plaintext,fontcolor=green]
tmp[shape=plaintext,fontcolor=blue]
head[shape=plaintext,fontcolor=red]
NULL[shape=plaintext]
node_t -> node2
tmp -> node1
head -> node2
node1:next -> node2
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
- `tmp->next = (*node)->next`: 改變 `node1` 的下一個節點為 `node3`
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> &node3}"]
node2 [label= " node2 |{ <value> 109 | <next> &node3}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
node_t[shape=plaintext,fontcolor=green]
tmp[shape=plaintext,fontcolor=blue]
head[shape=plaintext,fontcolor=red]
NULL[shape=plaintext]
node_t -> node2
tmp -> node1
head -> node2
node1:next -> node3
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
- `(*node)->next = tmp`: 最後再更改 `node2` 的下一個節點為 `node1` ，完成一次的節點交換
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> &node3}"]
node2 [label= " node2 |{ <value> 109 | <next> &node1}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
node_t[shape=plaintext,fontcolor=green]
tmp[shape=plaintext,fontcolor=blue]
head[shape=plaintext,fontcolor=red]
NULL[shape=plaintext]
node_t -> node2
tmp -> node1
head -> node2
node1:next -> node3
node2:next -> node1
node3:next -> node4
node4:next -> NULL
}
```
## `reverse`
```clike=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
CCC;
head = next;
}
return cursor;
}
```
`reverse` 做的是串列的反轉，例如: `1 -> 2 -> 3 -> 4` 變為 `4 -> 3 -> 2 -> 1` ，`CCC` 的選項有:
```
(a) cursor = head; head->next = cursor
(b) head->next = cursor; cursor = head
(c) cursor = head
(d) head->next = cursor
(e) head->next->next = cursor; cursor->next = head
(f) cursor->next = head; head->next->next = cursor
```
進入第5行的第一個迴圈，得到的串列如下圖所示:
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> &node2}"]
node2 [label= " node2 |{ <value> 109 | <next> &node3}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
cursor[shape=plaintext,fontcolor=green]
head[shape=plaintext,fontcolor=red]
next[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
cursor -> NULL
head -> node1
next -> node2
node1:next -> node2
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
觀察到指標 cursor 指向的是 NULL ，如同我們將原本為頭的指標改成指向 NULL 的尾端指標，所以裡面的選項中比較有可能的是 `a,d` ，又因為 `d` 選項沒有進一步對 cursor 做更動，並無法滿足功能實現的要求，所以較好的選項是 `b` ，完整程式碼如下:
```clike=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
head->next = cursor;
cursor = head;
head = next;
}
return cursor;
}
```
- `head->next = cursor`: 將 head 的下一個指標指向 NULL，等同將 head 指向的節點 `node1` 變為串列的尾端
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> NULL}"]
node2 [label= " node2 |{ <value> 109 | <next> &node3}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
cursor[shape=plaintext,fontcolor=green]
head[shape=plaintext,fontcolor=red]
next[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
cursor -> NULL
head -> node1
next -> node2
node1:next -> NULL
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
- `cursor = head`: 此時改變 cursor 指向的指標，作為新串列的頭指標
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> NULL}"]
node2 [label= " node2 |{ <value> 109 | <next> &node3}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
cursor[shape=plaintext,fontcolor=green]
head[shape=plaintext,fontcolor=red]
next[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
cursor -> node1
head -> node1
next -> node2
node1:next -> NULL
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
- `head = next`: 將 `head` 指標指回原串列的頭指標，即為 `next` 紀錄的節點 `node2`
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> NULL}"]
node2 [label= " node2 |{ <value> 109 | <next> &node3}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
cursor[shape=plaintext,fontcolor=green]
head[shape=plaintext,fontcolor=red]
next[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
cursor -> node1
head -> node2
next -> node2
node1:next -> NULL
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
- `node_t *next = head->next`:再看下一個迴圈，用 `next` 紀錄 `node3` 的節點
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> NULL}"]
node2 [label= " node2 |{ <value> 109 | <next> &node3}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
cursor[shape=plaintext,fontcolor=green]
head[shape=plaintext,fontcolor=red]
next[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
cursor -> node1
head -> node2
next -> node3
node1:next -> NULL
node2:next -> node3
node3:next -> node4
node4:next -> NULL
}
```
- `head->next = cursor`: 改變 node2 下一個指向的節點，指向 cursor 指向的節點 node1 ，等同將 `node2` 接在新串列的前端
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> NULL}"]
node2 [label= " node2 |{ <value> 109 | <next> &node1}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
cursor[shape=plaintext,fontcolor=green]
head[shape=plaintext,fontcolor=red]
next[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
cursor -> node1
head -> node2
next -> node3
node1:next -> NULL
node2:next -> node1
node3:next -> node4
node4:next -> NULL
}
```
- `cursor = head`: 改變新串列的頭指標 `cursor` 為 `node2`
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> &node2}"]
node2 [label= " node2 |{ <value> 109 | <next> &node1}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
cursor[shape=plaintext,fontcolor=green]
head[shape=plaintext,fontcolor=red]
next[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
cursor -> node2
head -> node2
next -> node3
node1:next -> NULL
node2:next -> node1
node3:next -> node4
node4:next -> NULL
}
```
- `head = next`: 將 head 重新指回原串列的頭指標，此時為 `node3`
```graphviz
digraph basic {
node [shape= record];
rankdir = LR
node1 [label= " node1 |{ <value> 72 | <next> NULL}"]
node2 [label= " node2 |{ <value> 109 | <next> &node1}"]
node3 [label= " node3 |{ <value> 110 | <next> &node4}"]
node4 [label= " node4 |{ <value> 111 | <next> NULL}"]
cursor[shape=plaintext,fontcolor=green]
head[shape=plaintext,fontcolor=red]
next[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext]
cursor -> node2
head -> node3
next -> node3
node1:next -> NULL
node2:next -> node1
node3:next -> node4
node4:next -> NULL
}
```
- 將所有原串列的節點都加入到頭指標為 `cursor` 的新串列後，即可透過 `cursor` 回傳我們想要的反轉串列
Google Drive
Gist
Clipboard
Sign in with Wallet
