# 2020q3 Homework1 (quiz1)
contributed by < `KairC` >
[Github](https://github.com/KairC/sysprog_quiz1/blob/master/quiz1.c)
---
## 程式運作原理
### void add_entry(node_t **head, int new_value)
* 目的：以 new_value 建立新的節點，並在傳入的 linked list 的尾端，加入新的節點。
* 方法：
* 傳入的參數 head 是一個指向 node_t 節點的指標的 address。
* 利用 pointer to pointer ，建立一個指標的指標，node_t **indirect，它能夠指向 head 或是 node->next ，因為這兩個變數都是用來指向 node_t 節點的指標。
* 對 indirect 取值，也就是 *direct ，可以得到 head 或 node->next 所儲存的資料，為一 node_t 節點的 address ，因此只要判斷 *direct 不是 NULL，就能夠確認 head 或 node->next 指向一個存在的 node_t 節點。
* 利用 indirect = &(*indirect)->next 改變 indirect 所指向的指標，當 *indirect 為 NULL ，代表 indirect 目前指向了 linked list 中最後一個用來指向 node_t 節點的指標，該指標指向了 NULL ，將該指標的值重新設定為新節點的 address，即完成加入新節點。
* Graphviz 圖例
* 將 indirect 指向 head
* 建立一個新節點 ，並用 new_node 指向它 (所謂"指向"，代表 new_node 儲存著新節點的記憶體位置)
```graphviz
digraph add_entry1 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
new_node [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">new_value</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [label="NULL" shape=none]
NULL_1 [label="NULL" shape=none]
new_node_ptr [label="new_node" shape=none]
node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c ->NULL_0 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
indirect [label="indirect" shape=none]
head [label="head" shape=none]
{rank=same new_node_ptr -> new_node}
{rank=same head->node_0 indirect->head [color=red]}
}
```
* 判斷 *indirect 是否為 NULL 。意思就是 indirect 所指向的指標，該指標的儲存內容是否為 NULL ，如果不是 NULL 就代表該指標確實有指向某一塊記憶體位置，反之就代表該指標指向 NULL 。
* 若不是 NULL 代表還沒到 linked list 的尾端，繼續往下一節點移動
```graphviz
digraph add_entry2 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
new_node [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">new_value</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [label="NULL" shape=none]
NULL_1 [label="NULL" shape=none]
new_node_ptr [label="new_node" shape=none]
node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c ->NULL_0 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
indirect [label="indirect" shape=none]
head [label="head" shape=none]
{rank=same new_node_ptr -> new_node}
{rank=same head->node_0 indirect->head [color=red]}
}
```
---
```graphviz
digraph add_entry3 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
new_node [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">new_value</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [label="NULL" shape=none]
NULL_1 [label="NULL" shape=none]
new_node_ptr [label="new_node" shape=none]
node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c ->NULL_0 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
indirect [label="indirect" shape=none]
useless [shape=none label=""]
useless->indirect [color=transparent]
head [label="head" shape=none]
{rank=same new_node_ptr -> new_node}
{rank=same useless head->node_0 }
indirect->node_0:next [color=red]
}
```
---
```graphviz
digraph add_entry4 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
new_node [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">new_value</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [label="NULL" shape=none]
NULL_1 [label="NULL" shape=none]
new_node_ptr [label="new_node" shape=none]
node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c ->NULL_0 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
indirect [label="indirect" shape=none]
head [label="head" shape=none]
{rank=same new_node_ptr -> new_node}
{rank=same head->node_0 }
{rank=same indirect->node_1:next [color=red]}
}
```
---
```graphviz
digraph add_entry5 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
new_node [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">new_value</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [label="NULL" shape=none]
NULL_1 [label="NULL" shape=none]
new_node_ptr [label="new_node" shape=none]
node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c ->NULL_0 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
indirect [label="indirect" shape=none]
head [label="head" shape=none]
{rank=same new_node_ptr -> new_node}
{rank=same head->node_0 }
{rank=same indirect->node_1:next [color=red]}
}
```
---
```graphviz
digraph add_entry6 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
new_node [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">new_value</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [label="NULL" shape=none]
NULL_1 [label="NULL" shape=none]
new_node_ptr [label="new_node" shape=none]
node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c ->NULL_0 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
indirect [label="indirect" shape=none]
head [label="head" shape=none]
{rank=same new_node_ptr -> new_node}
{rank=same head->node_0 }
{rank=same indirect->node_2:next [color=red]}
}
```
---
* 對於 indirect 指向的指標，改變其所儲存的內容。也就代表將該指標重新指向另外一塊記憶體位置。如此一來即可將 linked list 的尾端重新指向新的節點。
```graphviz
digraph add_entry7 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
new_node [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">new_value</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_1 [label="NULL" shape=none]
new_node_ptr [label="new_node" shape=none]
node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c ->new_node [arrowhead=normal arrowtail=dot tailclip=false dir=both]
new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
indirect [label="indirect" shape=none]
head [label="head" shape=none]
{rank=same new_node_ptr -> new_node}
{rank=same head->node_0 }
{rank=same indirect->node_2:next [color=red]}
}
```
### node_t *find_entry(node_t *head, int value)
* 目的：依照輸入的 value ，在 linked list 中找到第一個符合該 value 的節點。(若找不到會回傳 NULL ，但是該程式在後續並未對找不到做額外處理)
* 方法：建立 current 指標，指向 head 所指向的節點，在 linked list 上移動 current 以搜尋目標節點，在迴圈中止後回傳 current 所指向的記憶體位置。
* Graphviz 圖例：
```graphviz
digraph find_entry {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">target_value</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
current [shape=none label="current"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 current->node_0 [color=red]}
}
```
---
```graphviz
digraph find_entry {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">target_value</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
current [shape=none label="current"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 }
{rank=same current->node_1 [color=red]}
}
```
---
```graphviz
digraph find_entry {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">target_value</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
current [shape=none label="current"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 }
{rank=same current->node_2 [color=red]}
}
```
### void remove_entry(node_t **head, node_t *entry)
* 目的：移除目標節點。
* 方法：
* 利用 pointer to pointer ，可以將 head 與 node->next 看作一樣的東西，不必考慮移除第一個節點時還要搬動 head 的特殊情況。
* *indirect 可以得到當前 indirect 所指向的指標，其所指向的節點的記憶體位置。因此根據傳入的參數 entry ，可以得到欲移除的節點的記憶體位置，比較 *indirect 與 entry 即可確認是否已找到欲移除的節點。
* 找到目標節點後，更改 *indirect 所儲存的內容，即可將 *indirect 指向的節點改指向後一個節點，也就完成了移除。
* Graphviz 圖例：
```graphviz
digraph remove_entry {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">target_entry</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="indirect"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 indirect->head [color=red]}
}
```
---
```graphviz
digraph remove_entry {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">target_entry</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="indirect"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 }
{rank=same indirect->node_0:next [color=red]}
}
```
---
```graphviz
digraph remove_entry {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">target_entry</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="indirect"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 }
{rank=same indirect->node_1:next [color=red]}
}
```
---
```graphviz
digraph remove_entry {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">target_entry</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="indirect"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 }
{rank=same indirect->node_1:next [color=red]}
}
```
---
```graphviz
digraph remove_entry {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 }
}
```
### node_t *swap_pair(node_t *head)
* 目的：兩兩交換，i.e. 節點 0 與 節點 1 交換，節點 2 與 節點 3 交換，以此類推。
* 方法：
* 先假設要對第一個節點與第二個節點作交換，第三個節點與第四個節點作交換。
* 利用 pointer to pointer ，在 for-loop 的初始值設定時建立指標的指標 node_t **node 。
* 在 linked list 中，每一個節點必定會被一個指標指著，node_t **node 藉由指向該指標，可以在 *node 指向第二節點時得知第三個節點的記憶體位置。
* 如此一來就能將第一個節點改成指向第三個節點，並將第二節點改成指向第一個節點，即可完成交換。
* 最後再將 node_t **node 移往指向一個用來指向第三個節點的指標，也就是第二個節點的 next 。
* 再重複一次以上操作就能交換第三第四個節點。
* Graphviz 圖例：
```graphviz
digraph swap_pair1 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="node"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 indirect->head [color=red]}
}
```
---
```graphviz
digraph swap_pair2 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0" color="blue">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="node"]
tmp [shape=none label="tmp"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 indirect->head [color=red] }
{rank=same tmp->node_0 [color=blue]}
}
```
---
```graphviz
digraph swap_pair3 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0" color="blue">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="node"]
tmp [shape=none label="tmp"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1 indirect->head [color=red] }
{rank=same tmp->node_0 [color=blue]}
}
```
---
```graphviz
digraph swap_pair4 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0" color="blue">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>> group=1]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>> group=1]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>> group=1]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="node"]
tmp [shape=none label="tmp"]
node_0:next:c->node_2 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1 indirect->head [color=red] }
{rank=same tmp->node_0 [color=blue]}
}
```
---
```graphviz
digraph swap_pair5 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0" color="blue">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="node"]
tmp [shape=none label="tmp"]
node_0:next:c->node_2 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1 indirect->head [color=red] }
{rank=same tmp->node_0 [color=blue]}
}
```
---
```graphviz
digraph swap_pair6 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="node"]
node_0:next:c->node_2 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1 indirect->head [color=red] }
}
```
---
```graphviz
digraph swap_pair7 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="node"]
node_0:next:c->node_2 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false]
node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1}
{rank=same indirect->node_0:next [color=red]}
}
```
---
```graphviz
digraph swap_pair8 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0" color="blue"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="node"]
tmp [shape=none label="tmp"]
node_0:next:c->node_2 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false]
node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1}
{rank=same indirect->node_0:next [color=red]}
{rank=same tmp->node_2 [color=blue]}
}
```
---
```graphviz
digraph swap_pair9 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>> group=2]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>> group=2]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0" color="blue"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>> group=1]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>> group=1]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="node"]
tmp [shape=none label="tmp"]
{rank=same node_0:next:c->node_3 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false]}
node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1}
{rank=same indirect->node_0:next [color=red]}
node_2:next:c -> node_3 [tailclip=false arrowtail=dot dir=both]
{rank=same tmp->node_2 [color=blue]}
}
```
---
```graphviz
digraph swap_pair10 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0" color="blue"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>> ]
tmp [label="tmp" shape=none]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="node"]
node_0:next:c->node_3 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false]
node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1}
{rank=same indirect->node_0:next [color=red]}
{rank=same tmp->node_2 [color=blue] }
}
```
---
```graphviz
digraph swap_pair11 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0" color="blue"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0" color="red"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
indirect [shape=none label="node"]
tmp [shape=none label="tmp"]
node_0:next:c->node_3 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false]
node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1}
{rank=same indirect->node_0:next [color=red]}
{rank=same tmp->node_2 [color=blue]}
}
```
---
```graphviz
digraph swap_pair12 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
node_0:next:c->node_3 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false]
node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1}
}
```
### node_t *reverse(node_t *head)
* 目的：反轉 linked list
* 方法：
* 利用三個指標，cursor、head、next 各指向三個節點。
* 將 head 指向的節點，從原先指向 next 所指向的節點，改為指向 cursor 所指向的節點。
* 再將 cursor 重新指向 head 指向的節點， head 重新指向 next 指向的節點，如此不斷重複以上步驟，直到 head 指向了 NULL ，即完成反轉。
* 起始時先將 cursor 指向 NULL ，因為反轉後原先的 head 會成為最後一個 node ，而最後一個 node 會指向 NULL。
* Graphviz 圖例：
```graphviz
digraph reverse1 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
NULL_1 [shape=none label="NULL"]
cursor [shape=none label="cursor"]
NULL_1->node_0 [color=transparent]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 [color=red]}
{rank=same cursor->NULL_1 [color=blue]}
}
```
---
```graphviz
digraph reverse2 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
NULL_1 [shape=none label="NULL"]
cursor [shape=none label="cursor"]
next [shape=none label="next"]
NULL_1->node_0 [color=transparent]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 [color=red]}
{rank=same cursor->NULL_1 [color=blue]}
{rank=same next->node_1 [color=green]}
}
```
---
```graphviz
digraph reverse3 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
NULL_1 [shape=none label="NULL"]
cursor [shape=none label="cursor"]
next [shape=none label="next"]
node_0->node_1 [color=transparent]
NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same cursor->NULL_1 [color=blue]}
{rank=same head->node_0 [color=red]}
{rank=same next->node_1 [color=green]}
}
```
---
```graphviz
digraph reverse4 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
cursor [shape=none label="cursor"]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
NULL_1 [shape=none label="NULL"]
next [shape=none label="next"]
node_0->node_1 [color=transparent]
NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 [color=red]}
{rank=same cursor->node_0 [color=blue]}
{rank=same next->node_1 [color=green]}
}
```
---
```graphviz
digraph reverse5 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
NULL_1 [shape=none label="NULL"]
cursor [shape=none label="cursor"]
next [shape=none label="next"]
node_0->node_1 [color=transparent]
NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1 [color=red]}
{rank=same cursor->node_0 [color=blue]}
{rank=same next->node_1 [color=green]}
}
```
---
```graphviz
digraph reverse6 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
NULL_1 [shape=none label="NULL"]
cursor [shape=none label="cursor"]
next [shape=none label="next"]
node_0->node_1 [color=transparent]
NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1 [color=red]}
{rank=same cursor->node_0 [color=blue]}
{rank=same next->node_2 [color=green]}
}
```
---
```graphviz
digraph reverse7 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
NULL_1 [shape=none label="NULL"]
cursor [shape=none label="cursor"]
next [shape=none label="next"]
node_0->node_1 [color=transparent]
node_1->node_2 [color=transparent]
NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
node_0:next:c->node_1:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1 [color=red]}
{rank=same cursor->node_0 [color=blue]}
{rank=same next->node_2 [color=green]}
}
```
---
```graphviz
digraph reverse8 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
cursor [shape=none label="cursor"]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
NULL_1 [shape=none label="NULL"]
next [shape=none label="next"]
node_0->node_1 [color=transparent]
node_1->node_2 [color=transparent]
NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
node_0:next:c->node_1:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_1 [color=red]}
{rank=same cursor->node_1 [color=blue]}
{rank=same next->node_2 [color=green]}
}
```
---
```graphviz
digraph reverse9 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
cursor [shape=none label="cursor"]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
NULL_1 [shape=none label="NULL"]
next [shape=none label="next"]
node_0->node_1 [color=transparent]
node_1->node_2 [color=transparent]
NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
node_0:next:c->node_1:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_2 [color=red]}
{rank=same cursor->node_1 [color=blue]}
{rank=same next->node_2 [color=green]}
}
```
### void print_list(node_t *head)
* 目的：依序輸出 linked list 中所有的節點的 value 。
* 方法：利用 for-loop，建立指向 node_t 節點的指標 current，由 head 所指向的第一個節點開始，(1) 輸出 value ，(2) 將 current 往下一節點移動，重複以上步驟直到 current 指向 NULL 即完成依序輸出所有節點的 value 。
* Graphviz 圖例：
```graphviz
digraph print_list {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
current [shape=none label="current"]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 current->node_0 [color=red]}
}
```
---
```graphviz
digraph print_list {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
current [shape=none label="current"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 }
{rank=same current->node_1 [color=red]}
}
```
---
```graphviz
digraph print_list {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
current [shape=none label="current"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 }
{rank=same current->node_2 [color=red]}
}
```
---
```graphviz
digraph print_list {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">value_0</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_1</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_2</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0"> <tr>
<td port="data">value_3</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_0 [shape=none, label="NULL"]
head [shape=none, label="head"]
current [shape=none label="current"]
node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
{rank=same head->node_0 }
{rank=same current->node_3 [color=red]}
}
```
## 程式實際執行過程
* `node_t *head = NULL;`
```graphviz
digraph main1 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
head [label="head" shape=none]
NULL [label="NULL" shape=none]
{rank=same head->NULL}
}
```
---
* `add_entry(&head, 72);`
```graphviz
digraph main2 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
node_0:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
}
```
---
* `add_entry(&head, 101);`
```graphviz
digraph main3 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">101</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_1:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
}
```
---
* `add_entry(&head, 108);`
```graphviz
digraph main4 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">101</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
}
```
---
* `add_entry(&head, 109);`
```graphviz
digraph main5 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">101</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
}
```
---
* `add_entry(&head, 110);`
```graphviz
digraph main6 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">101</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
}
```
---
* `add_entry(&head, 111);`
```graphviz
digraph main7 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">101</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_5 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">111</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_4:next:c -> node_5 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_5:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
}
```
---
* `node_t *entry = find_entry(head, 101);`
```graphviz
digraph main8 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_1 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">101</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_5 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">111</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
entry [label="entry" shape=none]
node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_4:next:c -> node_5 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_5:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
{rank=same entry->node_1 [color=red]}
}
```
---
* `remove_entry(&head, entry);`
```graphviz
digraph main9 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_5 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">111</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
entry [label="entry" shape=none]
address [label="<memory address which has been freed>" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_4:next:c -> node_5 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_5:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
{rank=same entry->address [color=red]}
}
```
---
* `entry = find_entry(head, 111);`
```graphviz
digraph main10 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_5 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">111</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
entry [label="entry" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_4:next:c -> node_5 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_5:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
{rank=same entry->node_5 [color=red]}
}
```
---
* `remove_entry(&head, entry);`
```graphviz
digraph main11 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
entry [label="entry" shape=none]
address [label="<memory address which has been freed>" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
{rank=same entry->address [color=red]}
}
```
---
* `head = swap_pair(head);`
```graphviz
digraph main12 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
entry [label="entry" shape=none]
address [label="<memory address which has been freed>" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
{rank=same entry->address [color=red]}
}
```
---
* `head = reverse(head);`
```graphviz
digraph main13 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
entry [label="entry" shape=none]
address [label="<memory address which has been freed>" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
{rank=same entry->address [color=red]}
}
```
## 用指標的指標改寫 swap_pair 和 reverse
* 將傳入的參數 node_t *head 都改成指標的指標，也就是 node_t **head 。
* 將原先直接對 head 做操作的地方，都改成對指標的指標做操作，也就是將 head 代換成 *head_ptr ，可避免出現 `head = ... ` 的操作，雖然實際上一樣是在改變 head 儲存的記憶體位置。
* 最後以 `*head_pty = cursor` 直接將 *head_ptr ，也就是 head ，指向反轉後的第一個節點，達到避免回傳指標的目的。
```diff=
- node_t *swap_pair(node_t *head)
- {
- for (node_t **node = &head; *node && (*node)->next;
+ void swap_pair(node_t **head) {
+ for (node_t **node = head; *node && (*node)->next;
/*BB1*/ node = &(*node)->next->next) {
node_t *tmp = *node;
// BB2;
*node = (*node)->next;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
- return head;
}
```
```diff=
-node_t *reverse(node_t *head)
-{
- node_t *cursor = NULL;
- while (head) {
- node_t *next = head->next;
- // CCC;
- head->next = cursor;
- cursor = head;
- head = next;
- }
- return cursor;
+void reverse(node_t **head) {
+ node_t *cursor = NULL;
+ node_t **head_ptr = head;
+ while (*head_ptr) {
+ node_t *next = (*head_ptr)->next;
+ // CCC;
+ (*head_ptr)->next = cursor;
+ cursor = *head_ptr;
+ *head_ptr = next;
+ }
+ *head_ptr = cursor;
}
```
## 用遞迴改寫 reverse
* 終止條件：當 indirect 所指向的指標，該指標所指向的節點的 next 指向了 NULL，則終止遞迴，往回傳值。
* 回傳值一律為已完成反轉的 linked list 的最後一個節點的記憶體位置。
* 由於 head 會在遞迴的最後一層移往原始 linked list 的最後一個節點，因此會遺失原始的 linked list 的第一個節點的記憶體位置。需要額外建立 node_t *tail 指標去保留該節點的記憶體位置。
==往下遞迴==
```graphviz
digraph rev_recursive1 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
tail [label="tail" shape=none]
{rank=same tail->node_0}
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
indirect [label="indirect" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
{rank=same indirect->head [color=red]}
}
```
---
```graphviz
digraph rev_recursive2 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
tail [label="tail" shape=none]
{rank=same tail->node_0}
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
indirect [label="indirect" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
{rank=same indirect->node_0:next [color=red]}
}
```
---
```graphviz
digraph rev_recursive3 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
tail [label="tail" shape=none]
{rank=same tail->node_0}
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
indirect [label="indirect" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_0}
{rank=same indirect->node_2:next [color=red]}
}
```
---
==找到最後一個節點，將 head 指向它==
```graphviz
digraph rev_recursive4 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
tail [label="tail" shape=none]
{rank=same tail->node_0}
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
indirect [label="indirect" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_4}
{rank=same indirect->node_2:next [color=red]}
}
```
---
==開始回傳==
```graphviz
digraph rev_recursive5 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
tail [label="tail" shape=none]
{rank=same tail->node_0}
NULL_1 [label="NULL" shape=none]
head [label="head" shape=none]
indirect [label="indirect" shape=none]
tmp [label="tmp" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
{rank=same head->node_4 tmp->node_4 [color=blue]}
{rank=same indirect->node_2:next [color=red]}
}
```
---
```graphviz
digraph rev_recursive6 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
tail [label="tail" shape=none]
{rank=same tail->node_0}
head [label="head" shape=none]
indirect [label="indirect" shape=none]
tmp [label="tmp" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:s -> node_4:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
{rank=same head->node_4 tmp->node_4 [color=blue]}
{rank=same indirect->node_2:next [color=red]}
}
```
---
```graphviz
digraph rev_recursive7 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
tail [label="tail" shape=none]
{rank=same tail->node_0}
head [label="head" shape=none]
indirect [label="indirect" shape=none]
tmp [label="tmp" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_3:s -> node_4:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
{rank=same head->node_4 }
{rank=same indirect->node_0:next [color=red]}
{rank=same node_3 tmp->node_3 [color=blue]}
}
```
---
```graphviz
digraph rev_recursive8 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
tail [label="tail" shape=none]
{rank=same tail->node_0}
head [label="head" shape=none]
indirect [label="indirect" shape=none]
tmp [label="tmp" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:s -> node_3:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
node_3:s -> node_4:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
{rank=same head->node_4 }
{rank=same indirect->node_0:next [color=red]}
{rank=same node_3 tmp->node_3 [color=blue]}
}
```
==回到 void reverse(node_t **head)==
```graphviz
digraph rev_recursive9 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
tail [label="tail" shape=none]
{rank=same tail->node_0 [color=red]}
head [label="head" shape=none]
indirect [label="indirect" shape=none]
tmp [label="tmp" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_2:s -> node_3:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
node_3:s -> node_4:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
{rank=same head->node_4 }
{rank=same indirect->head}
{rank=same node_2 tmp->node_2 [color=blue]}
}
```
---
```graphviz
digraph rev_recursive10 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
tail [label="tail" shape=none]
{rank=same tail->node_0 [color=red]}
head [label="head" shape=none]
indirect [label="indirect" shape=none]
tmp [label="tmp" shape=none]
node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
node_0:s -> node_2:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
node_2:s -> node_3:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
node_3:s -> node_4:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
{rank=same head->node_4 }
{rank=same indirect->head}
{rank=same node_2 tmp->node_2 [color=blue]}
}
```
---
```graphviz
digraph rev_recursive11 {
rankdir=LR
node [color=black shape=none margin=0 height=.3 ]
node_0 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">108</td>
<td port="next"> </td>
</tr>
</table>>]
node_2 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">72</td>
<td port="next"> </td>
</tr>
</table>>]
node_3 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">110</td>
<td port="next"> </td>
</tr>
</table>>]
node_4 [label=<
<table border="0" cellborder="1" cellspacing="0">
<tr>
<td port="data">109</td>
<td port="next"> </td>
</tr>
</table>>]
tail [label="tail" shape=none]
{rank=same tail->node_0 [color=red]}
head [label="head" shape=none]
indirect [label="indirect" shape=none]
tmp [label="tmp" shape=none]
NULL [label="NULL" shape=none]
node_0:s -> node_2:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
node_2:s -> node_3:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
node_3:s -> node_4:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
NULL -> node_0 [color=transparent]
NULL:s -> node_0:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
{rank=same head->node_4 }
{rank=same indirect->head}
{rank=same node_2 tmp->node_2 [color=blue]}
}
```
## 實作 Fisher–Yates shuffle
* 對長度為 N 的 linked list，隨機骰出一數 k ， k 介於 1 到 N 之間
* 在 linked list 中找到第 k 個節點，將它移除並加入到新的 linked list 中。
* 重複以上兩步驟直到原先的 linked list 都被移除，即可得到經過隨機排列的 linked list 。
```clike=
node_t *pick_entry(node_t **head, node_t *entry) {
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
entry->next = NULL;
return entry;
}
void add_entry_(node_t **head, node_t *entry) {
node_t **indirect = head;
while (*indirect)
indirect = &(*indirect)->next;
*indirect = entry;
}
void FisherYates_shuffle(node_t **head) {
/* Get length of linked list */
int len = 0;
for (node_t **indirect = head; (*indirect); indirect = &(*indirect)->next)
len++;
if (len == 1)
return;
node_t *new_head = NULL;
srand(time(NULL));
for (; len > 0; len--) {
/* Roll */
int roll = (rand() % len) + 1;
/* Strike-out */
node_t **strike_out = head;
for (; roll > 1; roll--, strike_out = &(*strike_out)->next)
/* iterate */;
add_entry_(&new_head, pick_entry(head, *strike_out));
}
*head = new_head;
}
```
::: warning
延伸問題：
* 檢驗洗牌後的結果是否「足夠亂」，確認演算法的實作正確性
* 思考現在的實作是否可以改善？或者是否有對於 singlely-linked list 更有效率的 shuffle 方式？(考慮到 O(n)的 access)
:::
###### tags: `sysprog2020`
Sign in with Wallet
Connect another wallet