# 2020q3 Homework1 (quiz1)
contributed by < `sammer1107` >
###### tags: `進階電腦系統理論與實作`
[TOC]
## AA1 & AA2
```cpp=9
void add_entry(node_t **head, int new_value)
{
node_t **indirect = head;
node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
AA1;
while (*indirect)
indirect = &(*indirect)->next;
AA2;
}
```
### 程式理解
1. 13~15 行的地方我們已經要了新的記憶體，並在上面放入了新的值
2. 18~19 行的目的是要找到最後一個節點(當 next 為 NULL)
### AA1
根據上面的理解，**AA1** 不應該是 ```*indirect = new_node```，否則迴圈執行的結果永遠都是得到 NULL 後結束。因此 **AA1** 應是 assert(new_node)，檢查是否正確取得記憶體。
### AA2
找到最後一個節點後，需要將最後的 `next` 指標指向 `new_node`。迴圈結束時，`*indirect`相當於最後一個節點的 `next` ，故答案為 `*indirect = new_node`。
## BB1 & BB2
```c=42
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; BB1) {
node_t *tmp = *node;
BB2;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
### BB1
1. `swap_pair` 的功能為兩兩掉換，故 **BB1** 的功能是要連跳兩個 node。
3. 而且這裡我們是要改變 node 指向的位置而不是要修改 List 連接，故等號左邊要是 `node` 而不是 `*node`。
4. (a) 不對因為 `next` 的 type 為 `node_t*` ，故要再取址才是我們要的。
答案為 `(e) node = &(*node)->next->next`
### BB2
1. 在迴圈內我們要完成交換 Node 的工作，經過第 4 行後
```c=45
node_t *tmp = *node;
```
指標們長這樣，node1 與 node2 為目前要 swap 的節點。... 則代表前後延伸的節點
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
nodepp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">node</TD></TR>
</TABLE>>];
tmpp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">tmp</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node1</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node2</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
a:next:c -> b:val;
b:next:c -> c:val;
c:next:c -> d:val;
{
rank=same;
nodepp:p:s -> a:next:c;
}
{
rank=same; tmpp:p:s -> b:val;
}
}
```
:::warning
這樣表示 `node` 為指向前一節點的 `next` 的指標，`tmp` 則為指向第1節點的指標。
:::
2. 要把 node2 往前移的第一個動作就是把前一個節點的 `next` 牽往 node2。==做完後==長這樣
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
nodepp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">node</TD></TR>
</TABLE>>];
tmpp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">tmp</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node1</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node2</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
a:next:c -> b:val [style=invis]
a:next:c -> c:val;
b:next:c -> c:val;
c:next:c -> d:val;
{
rank=same;
nodepp:p:s -> a:next:c;
}
{
rank=same; tmpp:p:s -> b:val;
}
}
```
這裡我們要修改的是前一個 node 的 `next` 讓他指向 node2 ，故等號左邊應是 `*node`，而 node2 的位置為 `(*node)->next` (等於 node1 的 `next` )。故答案選 **(e)**
3. 下一行將後面的節點交手從 node2 交手給 node1。
```c=47
tmp->next = (*node)->next;
```
做完後長這樣
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
nodepp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">node</TD></TR>
</TABLE>>];
tmpp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">tmp</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node1</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node2</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c -> b [style=invis];
a -> b [style=invis];
a:next:c -> c:val;
b:next:c -> d:val;
c:next:c -> d:val;
{
rank=same;
nodepp:p:s -> a:next:c;
}
{
rank=same; tmpp:p:s -> b:val;
}
}
```
4. 最後將 node1 接在 node2 後面就完成了
```c=48
(*node)->next = tmp;
```
完成圖
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
nodepp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">node</TD></TR>
</TABLE>>];
tmpp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">tmp</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node1</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node2</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
a:next:c -> c:val;
b:next:c -> d:val;
c:next:c -> b:val;
{
rank=same;
nodepp:p:s -> a:next:c;
}
{
rank=same; tmpp:p:s -> b:val;
}
}
```
## CCC
```c=53
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
CCC;
head = next;
}
return cursor;
}
```
要 reverse linked list 我們需要兩個指標一前一後走到底，而 `cursor` 在這裡就是跟在 `head` 之後的指標。故選項要選 **(b)**`head->next = cursor; cursor = head`
，把 `head` 的 `next` 改為指向前一個節點，然後 `cursor` 和 `head` 各往前走一步。
### 第1次進迴圈的情況(57行)
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
head [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">head</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> node1 </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
cursor [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">cursor</TD></TR>
</TABLE>>];
null [label=<
<TABLE BORDER="0" CELLBORDER="0" cellspacing="0">
<TR><TD PORT="p">NULL</TD></TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node2</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node3</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> node4 </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
next [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">next</TD></TR>
</TABLE>>];
a:next:c -> b:val;
b:next:c -> c:val;
c:next:c -> d:val;
{
rank=same;
cursor:p:s -> null:n;
}
{
rank=same; head:p:s -> a:val;
}
{
rank=same; next:p:s -> b:val;
}
null -> a [style=invis]
}
```
做完 `head->next = cursor` 後
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
head [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">head</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val"> node1 </TD>
</TR>
</TABLE>>];
cursor [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">cursor</TD></TR>
</TABLE>>];
null [label=<
<TABLE BORDER="0" CELLBORDER="0" cellspacing="0">
<TR><TD PORT="p">NULL</TD></TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node2</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node3</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> node4 </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
next [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">next</TD></TR>
</TABLE>>];
null:p:e -> a:next:c [dir=back];
a:next:c -> b:val [style=invis];
b:next:c -> c:val;
c:next:c -> d:val;
{
rank=same;
cursor:p:s -> null:n;
}
{
rank=same; head:p:s -> a:val;
}
{
rank=same; next:p:s -> b:val;
}
}
```
`cursor = head` 後 `head=next`出回圈的樣子
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
head [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">head</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val"> node1 </TD>
</TR>
</TABLE>>];
cursor [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">cursor</TD></TR>
</TABLE>>];
null [label=<
<TABLE BORDER="0" CELLBORDER="0" cellspacing="0">
<TR><TD PORT="p">NULL</TD></TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node2</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node3</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> node4 </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
a:next:c -> b:val [style=invis];
b:next:c -> c:val;
c:next:c -> d:val;
{
rank=same;
cursor:p:s -> a:val:n;
}
{
rank=same; head:p:s -> b:val;
}
null:p:e -> a:next:c [dir=back]
}
```
### 第2次進迴圈的情況(57行)
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
head [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">head</TD></TR>
</TABLE>>];
next [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">next</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val"> node1 </TD>
</TR>
</TABLE>>];
cursor [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">cursor</TD></TR>
</TABLE>>];
null [label=<
<TABLE BORDER="0" CELLBORDER="0" cellspacing="0">
<TR><TD PORT="p">NULL</TD></TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node2</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node3</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> node4 </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
a:next:c -> b:val [style=invis];
b:next:c -> c:val;
c:next:c -> d:val;
{
rank=same;
cursor:p:s -> a:val:n;
}
{
rank=same; head:p:s -> b:val;
}
{
rank=same; next:p:s -> c:val;
}
null:p:e -> a:next:c [dir=back]
}
```
做完 `head->next = cursor` 後
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
head [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">head</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val"> node1 </TD>
</TR>
</TABLE>>];
next [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">next</TD></TR>
</TABLE>>];
cursor [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">cursor</TD></TR>
</TABLE>>];
null [label=<
<TABLE BORDER="0" CELLBORDER="0" cellspacing="0">
<TR><TD PORT="p">NULL</TD></TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val">node2</TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node3</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> node4 </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
a:val -> b:next:c [dir=back];
b:next:c -> c:val [style=invis];
c:next:c -> d:val;
{
rank=same;
cursor:p:s -> a:val:n;
}
{
rank=same; head:p:s -> b:val;
}
{
rank=same; next:p:s -> c:val;
}
null:p:e -> a:next:c [dir=back]
}
```
然後移動指標
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
head [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">head</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val"> node1 </TD>
</TR>
</TABLE>>];
cursor [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">cursor</TD></TR>
</TABLE>>];
null [label=<
<TABLE BORDER="0" CELLBORDER="0" cellspacing="0">
<TR><TD PORT="p">NULL</TD></TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val">node2</TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node3</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
null2 [label=<
<TABLE BORDER="0" CELLBORDER="0" cellspacing="0">
<TR><TD PORT="p">NULL</TD></TR>
</TABLE>>];
a:val -> b:next:c [dir=back];
b:next:c -> c:val [style=invis];
c:next:c -> d:val;
d:next:c -> null2:p:w
{
rank=same;
cursor:p:s -> b:val:n;
}
{
rank=same; head:p:s -> c:val;
}
null:p:e -> a:next:c [dir=back]
}
```
之後依此類推
### 結束時
結束時 `head` 到達最尾端的 `NULL`，cursor 則指向最後的節點，也就是新的頭，所以回傳 cursor。
## 延伸問題 2
### swap_pair 的 pointer to pointer 版本
```c=
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;
}
}
```
程式碼原理一致，再開頭時新的運作方式變成:
:::warning
括號 head 代表在 main 中的 head。
:::
1. 第5行
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
nodepp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">node</TD></TR>
</TABLE>>];
tmpp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">tmp</TD></TR>
</TABLE>>];
headp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">(head)</TD></TR>
</TABLE>>];
headpp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">head</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> node1 </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node2</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node3</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
a:next:c -> b:val;
b:next:c -> c:val;
c:next:c -> d:val;
nodepp:p:s -> headp:p:w;
{ rank=same; tmpp:p:s -> a:val; }
{ rank=same; headpp:p:s -> headp:p:n; }
headp:p:e -> a:val
}
```
2. 第 6 行
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
nodepp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">node</TD></TR>
</TABLE>>];
tmpp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">tmp</TD></TR>
</TABLE>>];
headp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">(head)</TD></TR>
</TABLE>>];
headpp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">head</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> node1 </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node2</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node3</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
a:next:c -> b:val;
b:next:c -> c:val;
c:next:c -> d:val;
nodepp:p:s -> headp:p:w;
{ rank=same; tmpp:p:s -> a:val; }
{ rank=same; headpp:p:s -> headp:p:n; }
headp:p:e -> b:val
headp:p:e -> a:val [style=invis]
}
```
3. 第 7 行
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
nodepp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">node</TD></TR>
</TABLE>>];
tmpp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">tmp</TD></TR>
</TABLE>>];
headp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">(head)</TD></TR>
</TABLE>>];
headpp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">head</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> node1 </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node2</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node3</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
a:next:c -> c:val;
b:next:c -> c:val;
c:next:c -> d:val;
nodepp:p:s -> headp:p:w;
{ rank=same; tmpp:p:s -> a:val; }
{ rank=same; headpp:p:s -> headp:p:n; }
headp:p:e -> b:val
b:p:e -> a:val [style=invis]
}
```
4. 第8行
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
nodepp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">node</TD></TR>
</TABLE>>];
tmpp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">tmp</TD></TR>
</TABLE>>];
headp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">(head)</TD></TR>
</TABLE>>];
headpp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">head</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> node1 </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node2</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node3</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
a:next:c -> c:val;
c:next:c -> d:val;
nodepp:p:s -> headp:p:w;
{ rank=same; tmpp:p:s -> a:val; }
{ rank=same; headpp:p:s -> headp:p:n; }
headp:p:e -> b:val
b:next:e -> a:val
}
```
`head` 在這裡很自然的指向了新的頭，所以完全不需要新增程式碼來處理這部份。
### reverse 的 pointer to pointer 版本
```C
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;
}
```
這個版本沒做什麼修改，只要將 `head` 都換成 `*head` 即可，回傳的動作則改成直接設定 `*head`。
## 延伸問題 3 - recursive reverse
```c=
node_t *reverse_recursive(node_t *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;
}
void reverse(node_t **head)
{
*head = reverse_recursive(*head);
}
```
### 程式解說
#### reverse
此函式是為了包裝 reverse 的呼叫成指標的型式，並會完成最後修改頭的動作。
#### reverse_recursive
1. 此函式把 linked list 拆成第一個節點以及後面整串，然後遞迴呼叫翻轉後面整串。
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
headp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">head</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node1</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey">
<TR>
<TD PORT="val">node2</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey">
<TR>
<TD PORT="val"> ... </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey">
<TR>
<TD PORT="val"> last node </TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
null [label=<
<TABLE BORDER="0" CELLBORDER="0" cellspacing="0">
<TR>
<TD PORT="p"> NULL </TD>
</TR>
</TABLE>>];
a:next:c -> b:val;
b:next:c -> c:val;
c:next:c -> d:val;
d:next:c -> null:p:w;
{
rank=same;
headp:p:s -> a:val;
}
}
```
2. 後面翻轉完後回傳的是後面那串新的頭。
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
headp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">head</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="val">node1</TD>
<TD PORT="next"> </TD>
</TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val">node2</TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val"> ... </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val"> last node </TD>
</TR>
</TABLE>>];
null [label=<
<TABLE BORDER="0" CELLBORDER="0" cellspacing="0">
<TR>
<TD PORT="p"> NULL </TD>
</TR>
</TABLE>>];
rev_head [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="p"> rev_head </TD>
</TR>
</TABLE>>];
a:next:c -> b:val;
a->null [style=invis]
b:val -> c:next:c [dir=back];
c:val -> d:next:c [dir=back];
null:p:e -> b:next:c [dir=back]
{
rank=same;
headp:p:s -> a:val;
}
{ rank=same; rev_head:p:s -> d:val}
}
```
3. 再來
```
head->next->next = head;
```
目的是要教第一個節點接回到尾巴。
最後再把尾巴的 `next` 設為 `NULL`:
```
head->next = NULL;
```
做完就變
```graphviz
digraph {
rankdir=LR;
node [shape=none];
edge [arrowhead=vee,headclip=false, tailclip=false]
headp [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR><TD PORT="p">head</TD></TR>
</TABLE>>];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val">node1</TD>
</TR>
</TABLE>>];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val">node2</TD>
</TR>
</TABLE>>];
c [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val"> ... </TD>
</TR>
</TABLE>>];
d [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey">
<TR>
<TD PORT="next"> </TD>
<TD PORT="val"> last node </TD>
</TR>
</TABLE>>];
null [label=<
<TABLE BORDER="0" CELLBORDER="0" cellspacing="0">
<TR>
<TD PORT="p"> NULL </TD>
</TR>
</TABLE>>];
rev_head [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD PORT="p"> rev_head </TD>
</TR>
</TABLE>>];
null:p:e -> a:next:c [dir=back];
b:val -> c:next:c [dir=back];
c:val -> d:next:c [dir=back];
a:val:e -> b:next:c [dir=back]
{
rank=same;
headp:p:s -> a:val;
}
{ rank=same; rev_head:p:s -> d:val}
}
```
回傳 `rev_head` 就完成了翻轉的動作。
## 延伸問題 4 - Fisher-Yates Shuffle
```c=
void shuffle(node_t **head){
node_t *old_head, *cursor, **indirect;
int range = 0;
old_head = cursor = *head;
// get list length
while(cursor){
range += 1;
cursor = cursor->next;
}
// starts Fisher-Yates
*head = NULL;
for(;range > 0; --range){
indirect = &old_head;
// move to selected node
for(int i = rand() % range;
i > 0; --i){
indirect = &(*indirect)->next;
}
// move selected node to new list
node_t *tmp = *indirect; // holds the node to move
*indirect = (*indirect)->next; // skip the node to move
tmp->next = *head; // move the node to the head of new list
*head = tmp;
}
}
```
### 程式解說
+ 6~8: 得到 list 長度，後面 Fisher-Yates 要用
+ 11: `*head` 作為新的 list 的頭
+ 12: Fisher-Yates Shuffle 的迴圈，出迴圈後就完成搬運所有節點了。head也將變成新的 list。
+ 15~17: 取得隨機數然後找到第 i 個節點
+ 20~23: 將這個節點從舊 list 移到新 list 的頭
Sign in with Wallet
Connect another wallet