# 2020q3 Homework1 (quiz1)
contributed by < `Tim096` >
- [**Linked List** 測驗題連結](https://hackmd.io/@sysprog/sysprog2020-quiz1)
- [作業區](https://hackmd.io/@sysprog/2020-homework1)
### Linked List 之 ADT
```c=
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
### 測驗題目需注意之重點
- Linked List 為**單向**
- 已知不存在 **circular (環狀結構)**
:::warning
**注意** :zap:
參考到< `RinHizakura` >的作業，提出一個很重要的觀點:
>**main(caller) 裡的 head pointer 的角度跟做為參數的 pointer to pointer 的 head是完全不同的**
>
`node_t *head = NULL;` 此為main(Caller)內的
`void add_entry(node_t **head, int new_value)` 參數的
:::
於2020/09/13參考到，讓困惑已久的自己終於解惑了
### Graphviz範例參考
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <data> 12 | <ref> }", width=1.2]
b [label="{ <data> 99 | <ref> }"];
c [label="{ <data> 37 | <ref> }"];
d [shape=box];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
參考以上圖+網路上的搜尋"[graphviz](https://graphviz.org/gallery/)"官網有許多的範例可以參考
### 針對運算子的複習
由於發現自己在上次測驗中，對於運算子，尤其是`&`和`*`及`->`的位階，相當不理解，故決定實驗看看讓自己理解，希望能搭配 Graphviz 讓自己理解。<br>
[Pointer to Pointer ~~Double Pointer~~ 參考資料](https://www.geeksforgeeks.org/double-pointer-pointer-pointer-c/)
假設今天有一段程式碼如下:
```cpp=
node_t *new_node = malloc(sizeof(node_t));
node_t *new_node_2 = malloc(sizeof(node_t));
node_t *head = &new_node;
node_t **indirect = head;
new_node->value = 1;
new_node->next = &new_node_2;
new_node_2->value = 2;
new_node_2->next = NULL;
```
呈現如下:
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
i [label="indirect|<ref> "];
a [label="head | <ref> "];
b [label="new_node |{ <data> 1 | <ref> }"];
c [label="new_node_2 |{ <data> 2 | <ref> }"];
d [label="Null"];
i:ref:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
與宅色夫老師畫的圖相比：
```mermaid
graph LR
subgraph linked list
head==>node1==>node2
end
subgraph pointer to pointer
indirect==>head
end
```
釐清並且整理觀念如下:
- `*new_node`得到的是一個`node_t`的 struct
- `*head`得到的是一個`node_t`的struct
- `(*new_node)->value`不等於`*new_node->value`，因為`->`的位階大於`*`
- `head = &new_node` 等於 `*indirect = new_node`(請務必記得最上面的**注意**)
### 針對原始測驗題的思考及理解
- `add_entry`
>新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy
#### 原始碼
```cpp=
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;
assert(new_node) #(AA1);
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node #(AA2);
}
```
此時各個的資料型別，初學者需要懂為何這些資料型別的判斷
Indirect = node **
*Indiect = node *
&head = node **
head = node *
p.s. : main裡面的head和add_entry當中的head的資料型別不相同
休息一下，開始講解程式碼
`add_entry`的流程如下：
1. **第3行** 建立指向 node 指標(`head`)的指標`indirect`
2. **第5行** 使用`malloc`分配記憶體空間給`new_node`
3. **第6~7行** 初始化`new_node`
4. **第5~7行** 簡單來說就是建立一個`new_node`
5. **(AA1)** 確定`new_node`是合法的
6. **第10~11行** 當取值 indirect 不是 NULL 時，indirect設為指向下一個值的位址的指標(`&(*indirect)->next`)
7. **(AA2)** 將此指標的值設為`new_node`
強烈建議自己拿筆畫圖看看~~~
```mermaid
graph LR
subgraph linked list
head==>node1==>node2
end
subgraph pointer to pointer
&head==>head
&head==>Indirect
Indirect==>head
end
```
:::warning
**注意** :zap:
- 此部分的Code使用於加 entry 於 linked list 的最後端(由**步驟五**可以得知)
- -> 的位階大於 & ，所以要先進行->運算再運算&
:::
如果**AA1**填入`*indirect = new_node`，會變成接在head指到的node的後方。
---
- `remove_entry`
>移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
```cpp=
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
`remove_entry`的流程如下：
1. **第3行** 建立指向 node 指標(`head`)的指標`indirect`
2. **第5~6行** 此部分最終目標是要將`indirect`指向 entry 。
方法是利用`while`從`head`開始找到指定的 entry ，若不是要找的entry，則走 next 往下一個。
3. **第8行** 將 Linked List 銜接回去
4. **第9行** 用`free`釋放 entry 占用的記憶體
---
- `swap_pair`
>交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3
#### 原始程式碼
```cpp=
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next #BB1) {
node_t *tmp = *node;
node = &(*node)->next #BB2;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
:::warning
:zap:**務必注意傳入函式內的是`node_t *head`**
:::
`swap_pair`的流程如下：
1. **第3行** `for`迴圈分別講解:
- `node_t **node = &head` 從`head`開始，此為建立指向 node 指標(`head`)的指標
- `*node && (*node)->next` 若無法形成兩兩一組，則結束for迴圈
- <font color="#f00">上網稍微查了一下大部分都是</font>`while (current.next != null && current.next.next != null)`<font color="#f00">不太懂為何for這樣寫可以?</font>
- **BB1** 因為是要兩個為一組進行操作，所以每個迴圈結束要跳兩個，根據運算子優先次序選擇`node = &(*node)->next->next`
2. **第4行** 複製`node`為暫存`tmp`
3. **第5~7行** 此為執行 swap 的部分，參見底下Graphviz呈現:
- **BB2** `node = &(*node)->next`
- `tmp->next = (*node)->next`
- `(*node)->next = tmp`
5. **第9行** 回傳`head`
#### Graphviz呈現
(取一部分當範例)
**第4行**前的狀況:
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
n [label="node | <ref> "];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="{ <data> 2 | <ref> } "];
node_3 [label="{ <data> 3 | <ref> } "];
n:ref:c -> node_1:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
**第4行`node_t *tmp = *node;`後**的狀況:
*node 可以取得head
head->next跟node_1->next是一樣的
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
n [label="node | <ref> "];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="{ <data> 2 | <ref> } "];
node_3 [label="{ <data> 3 | <ref> } "];
tmp [label="<ptr> tmp | { <data> 1 | <ref> } "];
node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n:ref:c -> node_1:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
tmp:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`node = &(*node)->next`
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="node|{ <data> 2 | <ref> } "];
node_3 [label="{ <data> 3 | <ref> } "];
tmp [label="tmp | { <data> 1 | <ref> } "];
node_1:ref:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
tmp:ref:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`tmp->next = (*node)->next`
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> node|{ <data> 2 | <ref> } "];
node_3 [label="{ <data> 3 | <ref> } "];
tmp [label="tmp | { <data> 1 | <ref> } "];
node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
tmp:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`(*node)->next = tmp`
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr>head|{ <data> 1(可忽略) | <ref> } "];
node_2 [label="<ptr> node|{ <data> 2 | <ref> } "];
node_3 [label="{ <data> 3 | <ref> } "];
tmp [label="tmp | { <data> 1 | <ref> } "];
node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
tmp:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> tmp [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
---
- `swap_pair` (簡易版理解版)
>交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3
#### 原始程式碼
```cpp=
node_t *swap_pair(node_t *head)
{
if (head == null) {
return null;
}
node_t **node = &head
node->next = head;
node_t temp = node;
node_t one = null;
node_t two = null;
while(temp->next!= null && temp->next->next!=null) {
one = temp->next;
two = temp->next->next;
one->next=two->next;
two->next = one;
temp->next = two;
temp = one;
}
return node->next;
}
```
- `reverse`:
>將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1
#### 原始程式碼
```cpp=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
head->next = cursor; cursor = head #CCC;
head = next;
}
return cursor;
}
```
:::warning
:zap:**務必注意傳入函式內的是`node_t *head`**
在操作每一個指標的時候，需要特別注意現在你操作的到底是甚麼型別，這樣才不會感覺在亂搞一通，自己也搞不清楚到底錯在哪裡?
:::
`reverse`的流程如下：
1. **第3行** 建立一指向`node_t`物件的指標`cursor`，先指向NULL
2. **第4~8行** 當 head 還有指向東西時，執行以下:
- 建立一指向`node_t`物件的指標`next`，指向 head 的 next
- **CCC** `head->next = cursor; cursor = head`這其實是兩行
- 將 head 的 next 設為 cursor
- 再把 cursor 變 head
- head 再接下去下一個物件
#### Graphviz呈現
`node_t *cursor = NULL;`
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
node_1 [label="head |{ <data> 1 | <ref> } "];
node_2 [label="{ <data> 2 | <ref> } "];
cursor [label="cursor | "];
node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`node_t *next = head->next;`
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
node_1 [label="head |{ <data> 1 | <ref> } "];
node_2 [label="{ <data> 2 | <ref> } "];
next [label="next |{<data> 2 |<ref> }"]
cursor [label="cursor |<data> "];
node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`head->next = cursor`
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
node_1 [label="head |{ <data> 1 | <ref> } "];
node_2 [label="{ <data> 2 | <ref> } "];
next [label="next |{<data> 2 |<ref> }"]
cursor [label="cursor | <ref> "];
node_1:ref:c -> cursor:ref [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`cursor = head`
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
node_1 [label="head(cursor) |{ <data> 1 | <ref> } "];
node_2 [label="{ <data> 2 | <ref> } "];
next [label="next |{<data> 2 |<ref> }"]
cursor [label=" <ref> "];
node_1:ref:c -> cursor:ref [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`head = next`
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
node_1 [label="head|{ <data> 1 | <ref> } "];
node_2 [label="{ <data> 2 | <ref> } "];
next [label="next(head) |{<data> 2 |<ref> }"]
cursor [label=" <ref> "];
node_1:ref:c -> cursor:ref [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
## 延伸問題
- 函式 `swap_pair` 和 `reverse` 對於指標的操作方式顯然異於 `add_entry` 及 `remove_entry`，需要額外做 `head = ...` 的更新，請用**指標的指標**來改寫，並避免回傳指標;
```cpp=
void 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;
}
}
```
<font color="#f00">Q : 這邊我搞不太懂這個不過就是修改了一下要不要回傳這一件事情而已，有甚麼重要的，不懂為何要出這一題目?</font>
A :
:::warning
參考< `sammer1107` >
:zap: 括號 head 代表在 main 中的 head。
:::
進入`for`迴圈:
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
n [label="node"];
head [label="head"];
head_main [label="(head)"];
node_1 [label="{node_1|<next>}"];
node_2 [label="{node_2|<next>}"];
node_3 [label="{node_3|<next>}"];
head -> head_main [arrowhead=vee, arrowtail=tail];
n -> head_main [arrowhead=vee, arrowtail=tail];
head_main -> node_1;
node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`node_t *tmp = *node;`
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
n [label="node"];
head [label="head"];
head_main [label="(head)"];
tmp [label="tmp"];
node_1 [label="{node_1|<next>}"];
node_2 [label="{node_2|<next>}"];
node_3 [label="{node_3|<next>}"];
head -> head_main [arrowhead=vee, arrowtail=tail];
n -> head_main [arrowhead=vee, arrowtail=tail];
head_main -> node_1;
tmp -> node_1;
node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`*node = (*node)->next;`
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
n [label="node"];
head [label="head"];
head_main [label="(head)"];
tmp [label="tmp"];
node_1 [label="{node_1|<next>}"];
node_2 [label="{node_2|<next>}"];
node_3 [label="{node_3|<next>}"];
head -> head_main [arrowhead=vee, arrowtail=tail];
n -> head_main [arrowhead=vee, arrowtail=tail];
head_main -> node_2;
tmp -> node_1;
node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`tmp->next = (*node)->next;`
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
n [label="node"];
head [label="head"];
head_main [label="(head)"];
tmp [label="tmp"];
node_1 [label="{node_1|<next>}"];
node_2 [label="{node_2|<next>}"];
node_3 [label="{node_3|<next>}"];
head -> head_main [arrowhead=vee, arrowtail=tail];
n -> head_main [arrowhead=vee, arrowtail=tail];
head_main -> node_2;
tmp -> node_1;
node_1:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`(*node)->next = tmp`
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
n [label="node"];
head [label="head"];
head_main [label="(head)"];
tmp [label="tmp"];
node_1 [label="{node_1|<next>}"];
node_2 [label="{node_2|<next>}"];
node_3 [label="{node_3|<next>}"];
head -> head_main [arrowhead=vee, arrowtail=tail];
n -> head_main [arrowhead=vee, arrowtail=tail];
head_main -> node_2;
tmp -> node_1;
node_1:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:next:c -> node_1[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
---
```cpp=
void reverse(node_t **head)
{
node_t *cursor = NULL;
while (*head) {
node_t *next = (*head)->next;
(*head)->next = cursor;
cursor = *head;
*head = next;
}
*head = cursor;
}
```
<font color="#f00">Q : 這邊我搞不太懂這個不過就是修改了一下要不要回傳這一件事情而已，有甚麼重要的，不懂為何要出這一題目? (和上面一樣的問題)，頂多這邊多修改了一點傳入的值，但是也看不出來重要性在哪?</font>
A :
---
- 以遞迴改寫上述的 `reverse`，注意，你可能因此需要建立新的函式，如 `rev_recursive`，隨後在 `reverse` 函式中呼叫 `rev_recursive`;
```cpp=
node_t *rev_reverse(node_t *head)
{
# If there isn't any node left or not even node, return head.
if(!head || !head->next){
return head;
}
node_t *rev_head = reverse_recursive(head->next);
head->next->next = head;
head->next = NULL;
return rev_head;
}
```
<font color="#f00">Q : 這邊程式碼當中的第4行的部分為何需要`!head `這一個部分不可能沒有head吧 ? (是否是因為怕電腦出問題而設置的呢 ? )簡單來說非程式開發員所導致的錯誤</font>
A :
藉著 rev_recursive 函式`node_t *rev_head = reverse_recursive(head->next);`把 linked list 拆成第一個節點以及後面整個節點 List <br>
原圖:
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
head [label="head"];
node_1 [label="{node_1|<next>}"];
node_2 [label="{node_2|<next>}"];
node_3 [label="{node_3|<next>}"];
head -> node_1;
node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_3:next:c -> null[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
經前面 recursive 的部分後:
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
head [label="head"];
node_1 [label="{node_1|<next>}"];
node_2 [label="{node_2|<next>}"];
node_3 [label="{node_3|<next>}"];
head -> node_1;
node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:next:c -> null[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_3:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
rev_head -> node_3
}
```
`head->next->next = head;`
`head->next = NULL;`
`head->next->next`便是`node_2->next`，將其設為`head`，然後再將最後的`next`指向NULL如底下:
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
head [label="head"];
node_1 [label="{node_1|<next>}"];
node_2 [label="{node_2|<next>}"];
node_3 [label="{node_3|<next>}"];
head -> node_1;
node_1:next:c -> null[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:next:c -> node_1[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_3:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
rev_head -> node_3
}
```
利用上面完成了 reverse，最後用`void reverse`配合**pointer to pointer**修飾，程式碼如下:
```cpp=
void reverse(node_t **head)
{
*head = rev_recursive(*head);
}
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
head [label="(head)"];
head_ptr [label="head"];
node_1 [label="{node_1|<next>}"];
node_2 [label="{node_2|<next>}"];
node_3 [label="{node_3|<next>}"];
head -> node_1;
head_ptr -> rev_head
node_1:next:c -> null[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:next:c -> node_1[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_3:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
rev_head -> node_3
}
```
可藉此發現原始的 main 中的`head`並不會動到！
---
- 針對 `singly-linked list` 的節點，實作 **Fisher–Yates shuffle**，你應該儘量降低記憶體的使用量;
[Fisher–Yates shuffle Wiki](https://en.wikipedia.org/wiki/Fisher–Yates_shuffle)
演算法如下：
```
To shuffle an array a of n elements (indices 0..n-1):
for i from n - 1 downto 1 do
j = random integer with 0 <= j <= i
exchange a[j] and a[i]
```
```cpp=
void randomize ( node_t **head ){
// Use a different seed value so that we don't get same
// result each time we run this program
srand ( time(NULL) );
node_t *old_head, *cursor, **indirect;
int range = 0;
old_head = cursor = *head;
// get list length
while(cursor){
range += 1;
cursor = cursor->next;
}
*head = NULL;
for(;range > 0; --range){
// Start from old head
indirect = &old_head;
// move to selected node
for(int i = rand() % range;i > 0; --i)
indirect = &(*indirect)->next;
// move selected node to new list
// Down below is the part for swapping
node_t *tmp = *indirect;
*indirect = (*indirect)->next;
tmp->next = *head;
*head = tmp;
}
}
```
###### tags: `進階電腦系統應用2020` `quiz0`
Sign in with Wallet
Connect another wallet