---
title:
image:
description:
tags: NCKU Class , 進階電腦系統理論與實作 , 2020q3
---

# 2020q3 Homework1 (quiz1)
contributed by < `TsenEN` >
* [指標的解說](https://reurl.cc/Q34Rxb)
* [題目](https://reurl.cc/R1OyoD)
* [共筆區](https://reurl.cc/n0ZLd1)

## Link list structure Definition

typedef struct __node {                   
    int value;
    struct __node *next;
} node_t

## add_entry()

void add_entry(node_t **head, int new_value)
{
    node_t **indirect = head;

    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;

    AA1
    while (*indirect)
        indirect = &(*indirect)->next;

    AA2
}

### `AA1`
- [x] `(a)` `assert(new_node)`
- [ ] `(b)` `*indirect = new_node`

### `AA2`
- [ ] `(a)` `assert(new_node)`
- [x] `(b)` `*indirect = new_node`

### 程式分析
#### Argument

void add_entry(node_t **head, int new_value)

為何需要它們?
* 你要插入 link list 就需要知道排頭在哪 (head)，就好像你排隊也要知道從哪裡開始排隊一樣。
* value 就是你想配置新 node 的值。

#### 配置新空間

node_t **indirect = head;

node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;

assert(new_node);

為甚麼需要`node_t **indirect = head`，我動 head 就好啦？
* pointer to pointer 的用意(注意這邊的 `node_(no.)`並沒有儲存 link list 只是方便好看)：
* 首先要知道何謂 [Call by value](https://reurl.cc/6lNvEd)，另外在 K&R 在其原著 "The C programming language" 中有提到 C 語言只有 <font color = red>Call by value</font> ，可以參考這篇 [c 語言有沒有 call by reference(or call by address) ?](https://reurl.cc/VX8zoQ)
:::danger
:warning: 共筆提及的超連結 (hyperlink) 的標題應具備一定的資訊量，也就是說儘量用原本的標題或者在原有的標題基礎加以潤飾，避免寫 `link 1` 和 `link 2`，後者無助於閱讀。
另外，共筆書寫不該有太深的縮排 (indention)，否則會造成閱讀困難。寫共筆就是為了給人看，讓人指教
:notes: jserv
:::
> 好的謝謝老師🙏
> [name=TsenEN]

假設 `0x7fff86ae7208` 是 `head` 的記憶體位址，它放的是 `node_1` 的起始位址，如果今天傳入參數是:
| Name | 記憶體位置 | Value |
| ------------ | -------------- | -------------- |
| head | 0x7fff86ae7208 | 0x7fff86ae7240 |
| node_1_value | 0x7fff86ae7240 | 72 |
| node_1_next | 0x7fff86ae7244 | 0x7fff86ae7280 |
| .. | .. | .. |
| node_2_value | 0x7fff86ae7280 | 101 |
* 先看一下這篇 [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list) 這篇可以發現新世界！
* `node_t *head`，這拿到的直接是一個 head 的記憶體位置`0x7fff86ae7208`(下圖紅色的 head)，如果今天是用這個做在 dereference `*indirect` 這樣你會直接存取到 link list 的串列頭(`node_1`)，仍然可以做新增的動作，但你需要去做邊界判斷(意思就是你是否在 list 頭尾，在的話需要做不一樣的操作方式)，就要像剛剛上面那篇去做判斷!
* `node_t **head`，這拿到的會是一個"指著" head 記憶體位置的指標，他的記憶體位置假設是`0x7fff86ae721C`(配合`node_t **indirect = head` 那麼 indirect 就是那個"指著" head 記憶體位置的指標)，妳可以透過移動這個 head 指標來操作，這樣的方式可以不用去做邊界判斷。

| Name | 記憶體位置 | Value |
| ------------ | -------------- | -------------- |
| head | 0x7fff86ae7208 | 0x7fff86ae7240 |
| .. | .. | .. |
| indirect | 0x7fff86ae721C | 0x7fff86ae7208 |
| .. | .. | .. |
| node_1_value | 0x7fff86ae7240 | 72 |
| node_1_next | 0x7fff86ae7244 | 0x7fff86ae7280 |
| .. | .. | .. |
| node_2_value | 0x7fff86ae7280 | 101 |

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        indirect[shape=plaintext,fontcolor=blue]

        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        Nil [shape=plaintext];

        A:next:c -> B:val;
        B:next:c -> Nil:w;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            indirect -> head;
            head:p:s -> A;
        }

}

assert(new_node) 主要是確認新的 node 是否有配置到，但建議是放14行 malloc 後就確認。

    node_t **indirect = head;

    node_t *new_node = malloc(sizeof(node_t));
    assert(new_node);
    new_node->value = new_value;
    new_node->next = NULL;

#### 找到最尾端

    while (*indirect)
        indirect = &(*indirect)->next;

    *indirect = new_node;

* `*indirect` 他得到的會是一個 node 的位址，所以沒有到 Nil 就不會跳出去。
* `indirect = &(*indirect)->next` 首先 &* 對電腦來說執行順序地位一樣所以要加 "()" ，node 位址`(*indirect)` 的 next 就是下一個 node ，再加 & 取址 assign 給 indirect，就會得到下一個 node 的位址。
* `*indirect = new_node` 因為 indirect 循著 link list 來到最後 Nil 的地方( node_2 所指向的地方 )，所以我們將 new_node assign 給`*indirect` 這個位址作為更新就插到最後面了。
* <font color = 'red' >注意 indirect 指標所指的位址是在那個 node 的 next ，而不是直接跳過去指向那個整個 node </font>，這樣當 while 跑到最後一個 node 去看到它下一個 next 是 Nil，就會跳出 while ，再將 new_node address assign 到 last node 的 next 。

* `add_entry(&head, 108)`
#### 1.

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        indirect[shape=plaintext,fontcolor=blue]

        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">new_node</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];
            
        Nil [shape=plaintext];

        A:next:c -> B:val;
        B:next:c -> Nil:w;
        C:next:c -> Nil:w;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            indirect -> head;
            head:p:s -> A;
        }

}

#### 2.

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        indirect[shape=plaintext,fontcolor=blue]

        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
            
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">new_node</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        Nil [shape=plaintext];

        A:next:c -> B:val;
        B:next:c -> Nil:w;
        C:next:c -> Nil:w;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            head:p:s -> A;
        }
                {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            indirect -> A:next;
        }

}

#### 3.

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        indirect[shape=plaintext,fontcolor=blue]

        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
            
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">new_node</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        Nil [shape=plaintext];

        A:next:c -> B:val;
        B:next:c -> Nil:w;
        C:next:c -> Nil:w;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            head:p:s -> A;
        }
        
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            indirect -> B:next;
        }

}

#### 4.

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        indirect[shape=plaintext,fontcolor=blue]

        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
            
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">new_node</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        Nil [shape=plaintext];

        A:next:c -> B:val;
        B:next:c -> C:val;
        C:next:c -> Nil:w;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            head:p:s -> A;
        }
        
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            indirect -> C;
        }

}

## find_entry()

node_t *find_entry(node_t *head, int value)
{
    node_t *current = head;
    for (; current && current->value != value; current = current->next)
        /* interate */;
    return current;
}

### 程式分析

#### Argument

node_t *find_entry(node_t *head, int value)

程式的用意在於我要找到指定的 node ，那個 node 在哪裡就需要回傳一個記憶體位址，所以我們傳入的引數跟回傳參數都有小細節要注意。
* `*find_entey` 加個 ” * “ 就是因為你要回傳”位址“。
* `node_t *head` 這邊就是個很好的例子( “ ** ” v.s. “ * “)，今天我只是需要先確認這個 value 是否有在 list 裡，有的話就傳回位址，“不需要特別去操作指標”所以不用“ ** ”。

#### 尋找目標值

for (; current && current->value != value; current = current->next)
        /* interate */;

for裡面終止條件為 `current && current->value != value` ，左邊確定是否到 Nil ，右邊在做 vlaue 比對，沒找到就 `current = current->next` 直到碰到 Nil。

#### 回傳為址

return current;

* `node_t *entry = find_entry(head, 101);`
關於 struct 在記憶體配置空間的藝術可參考這篇 [C 語言:關於 sizeof 及結構的記憶體對齊](https://reurl.cc/v1klQa)。

假設 node_t 裡面存" value "跟" 記憶體位址 " 都為 4 bytes ，`node_2` 始位址為 `0x7fff86ae7280`。

#### 1.
| Name | 記憶體位置 | Value |
| ------------ | -------------- | -------------- |
| head | 0x7fff86ae7208 | 0x7fff86ae7240 |
| .. | .. | .. |
| current | 0x7fff86ae721C | 0x7fff86ae7240 |
| .. | .. | .. |
| node_1_value | 0x7fff86ae7240 | 72 |
| node_1_next | 0x7fff86ae7244 | 0x7fff86ae7280 |
| .. | .. | .. |
| node_2_value | 0x7fff86ae7280 | 101 |
<font size = 3 >value = 101</font>

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        current[shape=plaintext,fontcolor=blue]
            
        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
            
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">new_node</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        Nil [shape=plaintext];

        A:next:c -> B:val;
        B:next:c -> C:val;
        C:next:c -> Nil:w;
        
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            head:p:s -> A;
        }
                {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            current:p:s -> A:value;
        }


}

#### 2.
| Name | 記憶體位置 | Value |
| ------------ | -------------- | -------------- |
| head | 0x7fff86ae7208 | 0x7fff86ae7240 |
| .. | .. | .. |
| current | 0x7fff86ae721C | 0x7fff86ae7280 |
| .. | .. | .. |
| node_1_value | 0x7fff86ae7240 | 72 |
| node_1_next | 0x7fff86ae7244 | 0x7fff86ae7280 |
| .. | .. | .. |
| node_2_value | 0x7fff86ae7280 | 101 |
<font size = 3 >value = 101
current = 0x7fff86ae7280</font>

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        current[shape=plaintext,fontcolor=blue]
        
        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
            
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_3</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        Nil [shape=plaintext];

        A:next:c -> B:val;
        B:next:c -> C:val;
        C:next:c -> Nil:w;
        
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            head:p:s -> A;
        }
                {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            current:p:s -> B:value;
        }


}

因為 `current->value != value` 不成立跳出 for，`return curret`。

## remove_entry()
<font size = 5>以 remove node_2 為例 entry = 0x7fff86ae7280</font>

void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    *indirect = entry->next;
    free(entry);
}

### 程式分析

#### Argument

void remove_entry(node_t **head, node_t *entry)

刪除某 link list 的某個 node ，需要 link list (`node_t **head`)跟那個要刪除點的"記憶體位址"(`node_t *entry`)。

#### 尋找 node

    node_t **indirect = head;

    while ((*indirect) != entry)
        indirect = &(*indirect)->next; 

`while ((*indirect) != entry)` 一開始 indirect 指向的是 `head` ，透過 dereference `(*indirect)` 變成 `node_1` 的起始位址來跟 `entry` 做比較，位址對就跳出 while 不對就將它這個 node 的 next assign 給 `indirect`。

#### 1.

| Name | 記憶體位置 | Value |
| ------------ | -------------- | -------------- |
| head | 0x7fff86ae7208 | 0x7fff86ae7240 |
| .. | .. | .. |
| indirect | 0x7fff86ae721C | 0x7fff86ae7208 |
| .. | .. | .. |
| node_1_value | 0x7fff86ae7240 | 72 |
| node_1_next | 0x7fff86ae7244 | 0x7fff86ae7280 |
| .. | .. | .. |
| node_2_value | 0x7fff86ae7280 | 101 |

*indirect = 0x7fff86ae7240
entry = 0x7fff86ae7280

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        indirect[shape=plaintext,fontcolor=blue]
            
        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">new_node</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];
            
        Nil [shape=plaintext];

        A:next:c -> B:val;
        B:next:c -> C:val;
        C:next:c -> Nil:w;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            indirect -> head;
            head:p:s -> A;
        }

}

0x7fff86ae7240 不等於 0x7fff86ae7280

`(*indirect) != entry` 成立所以繼續執行 while，`indirect = &(*indirect)->next;` 所以 `indirect = 0x7fff86ae7244 `(是 node -> next 的位址不是裡面的值)。

#### 2.

| Name | 記憶體位置 | Value |
| ------------ | -------------- | -------------- |
| head | 0x7fff86ae7208 | 0x7fff86ae7240 |
| .. | .. | .. |
| indirect | 0x7fff86ae721C | 0x7fff86ae7244 |
| .. | .. | .. |
| node_1_value | 0x7fff86ae7240 | 72 |
| node_1_next | 0x7fff86ae7244 | 0x7fff86ae7280 |
| .. | .. | .. |
| node_2_value | 0x7fff86ae7280 | 101 |
*indirect = 0x7fff86ae7280
entry = 0x7fff86ae7280

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        indirect[shape=plaintext,fontcolor=blue]

        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">new_node</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];
            
        Nil [shape=plaintext];

        A:next:c -> B:val;
        B:next:c -> C:val;
        C:next:c -> Nil:w;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            head:p:s -> A;
        }
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            indirect -> A:next;

        }

}

`(*indirect) != entry` 不成立所以跳出 while。
#### 斷開連結

    *indirect = entry->next;

找到目標 node 當然我們就要斷開魂結，透過 `indirect` 指著 `node_1` 的 next 來修改。

#### 3.

| Name | 記憶體位置 | Value |
| ------------ | -------------- | -------------- |
| head | 0x7fff86ae7208 | 0x7fff86ae7240 |
| .. | .. | .. |
| indirect | 0x7fff86ae721C | 0x7fff86ae7244 |
| .. | .. | .. |
| node_1_value | 0x7fff86ae7240 | 72 |
| node_1_next | 0x7fff86ae7244 | 0x7fff86ae7280 |
| .. | .. | .. |
| node_2_value | 0x7fff86ae7280 | 101 |
| .. | .. | .. |
| node_2_next | 0x7fff86ae72C0 | 0x7fff86ae72C8 |
| .. | .. | .. |
| node_3_value | 0x7fff86ae72C8 | 108 |

*indirect = 0x7fff86ae7280
entry = 0x7fff86ae7280
entry->next = 0x7fff86ae72C8

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        indirect[shape=plaintext,fontcolor=blue]

        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">new_node</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];
            
        Nil [shape=plaintext];

        A:next:c -> C:val;
        B:next:c -> C:val;
        C:next:c -> Nil:w;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            head:p:s -> A;
        }
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            indirect -> A:next;

        }

}

#### 釋放空間

free(entry);

#### 4.

| Name | 記憶體位置 | Value |
| ------------ | -------------- | -------------- |
| head | 0x7fff86ae7208 | 0x7fff86ae7240 |
| .. | .. | .. |
| indirect | 0x7fff86ae721C | 0x7fff86ae7244 |
| .. | .. | .. |
| node_1_value | 0x7fff86ae7240 | 72 |
| node_1_next | 0x7fff86ae7244 | 0x7fff86ae72C8 |
| .. | .. | .. |
| node_3_value | 0x7fff86ae72C8 | 108 |

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        indirect[shape=plaintext,fontcolor=blue]

        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">new_node</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];
            
        Nil [shape=plaintext];

        A:next:c -> C:val;
        C:next:c -> Nil:w;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            head:p:s -> A;
        }
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            indirect -> A:next;

        }

}

## swap_pair()
程式用意請看 [ Leet code 24. Swap Nodes in Pairs ](https://leetcode.com/problems/swap-nodes-in-pairs/)

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;
}

### 解題思路

Argument 傳入的是 `head` 指標裡指著 `node_1` 的位址，pointer to pointer (`node`) 是存放 `head` 指標的實體位址，這邊可以思考為何需要 pointer to pointer ?
* 當你看到題目心中應該會有兩個做法 (1)交換 Value (2)修改 link next，這邊的做法是 (2) ，先前在 `add_entry()` 提過一下子`* & ** `用法上的差異，透過圖形化應該比較有感覺了吧 ? 這種方式就是為了通過<font color ='red'>存取每個 node 的 next 的實體位址來直接修改它存放的值</font>，這樣就是直接修改 next 所指向的地方。

### `BB1`
- [ ] `(a)` `node = (*node)->next->next`
- [ ] `(b)` `*node = (*node)->next->next`
- [ ] `(c)` `*node = ((*node)->next)->next`
- [ ] `(d)` `*node = &((*node)->next)->next`
- [x] `(e)` `node = &(*node)->next->next`
- [ ] `(f)` `*node = &(*node)->next->next`

### `BB2`
- [ ] `(a)` `node = (*node)->next`
- [ ] `(b)` `node = &(*node)->next`
- [x] `(c)` `*node = (*node)->next`
- [ ] `(d)` `*node = &(*node)->next`
- [ ] `(e)` `*node = &((*node)->next)`

假設目前 link list 為 72->101->108->109 目標是 101->72->109->108

先來想看看 BB1，for(`1`;`2`;`3`) 迴圈第`3`個值是我們變數`1` 更新的規律(可能`+ - * / `或者等等其他操作)，先看了一下變數`1` 發現是一個存放 pointer 變數 (`node`)，那竟然是 link list 想必一定會透過 next 來去更新位址來移動，所以我們可以想喔喔大概是 node = xxx -> next 之類的。

有了 BB1 雛型接著往下看程式很快遇到 BB2，如果大家寫過 swap 兩個變數交換數值的會知道需要額外一個變數來暫存數值。
* 假設今天 A = 72 , B = 101 目標是 A = 101 , B = 72，如果只用兩個變數是無法做到交換的，譬如你寫 A = B (B 把值 assign 給 A)， 72 這個數值就會被蓋掉，所以需要一個數值( C )額外暫存。
想法大概是這樣:
C = A
A = B
B = C

digraph g {
node [shape=none];
  A->C;
  B->A;
  C->B;  
}

所以想想 link list 要交換什麼才算換了位置，答案就是 next 所指的方向 ! 所以我們這邊大概有了 BB2 雛型應該是什麼了 !

| Name | 記憶體位置 | Value |
| ------------ | -------------- | -------------- |
| head | 0x7fff86ae7208 | 0x7fff86ae7240 |
| .. | .. | .. |
| nodepp | 0x7fff86ae721C | 0x7fff86ae7208 |
| .. | .. | .. |
| tmp | 0x7fff86ae7220 | 0x7fff86ae7240 |
| .. | .. | .. |
| node_1_value | 0x7fff86ae7240 | 72 |
| node_1_next | 0x7fff86ae7244 | 0x7fff86ae7280 |
| .. | .. | .. |
| node_2_value | 0x7fff86ae7280 | 101 |
| .. | .. | .. |
| node_2_next | 0x7fff86ae72C0 | 0x7fff86ae72C8 |
| .. | .. | .. |

#### 1.

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        nodepp[shape=plaintext,fontcolor=blue]
        tmp[shape=plaintext,fontcolor=orange]
        
        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_3</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];
         D [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_4</TD>
                  <TD PORT="val">109</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];    
            
        Nil [shape=plaintext];

        A:next:c -> B:val;
        B:next:c -> C:val;
        C:next:c -> D:val;
        D:next:c -> Nil:w;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            head:p:s -> A;
        }
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            nodepp -> head;
        }
                {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=LR; 
            tmp:p:s -> A;
        }

}

#### 2.(錯誤)
那我們依樣畫葫蘆，下面這樣大錯特錯 ! 因為沒注意到 `head` 已經改變，再者沒有了解到 tmp 跟 node 在這個題目是用來幹嘛的 !

tmp = tmp->next;
tmp->next = (*node)->next;
(*node)->next = tmp;

照著上面程式碼做
( nodepp = `node_t **node = &head` 那個 `node` 變數的代稱)
| Name | 記憶體位置 | Value |
| ------------ | -------------- | -------------- |
| head | 0x7fff86ae7208 | 0x7fff86ae7240 |
| .. | .. | .. |
| nodepp | 0x7fff86ae721C | 0x7fff86ae7208 |
| .. | .. | .. |
| tmp | 0x7fff86ae7220 | 0x7fff86ae7280 |
| .. | .. | .. |
| node_1_value | 0x7fff86ae7240 | 72 |
| node_1_next | 0x7fff86ae7244 | 0x7fff86ae7280 |
| .. | .. | .. |
| node_2_value | 0x7fff86ae7280 | 101 |
| .. | .. | .. |
| node_2_next | 0x7fff86ae72C0 | 0x7fff86ae7280 |
| .. | .. | .. |

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        nodepp[shape=plaintext,fontcolor=blue]
        tmp[shape=plaintext,fontcolor=orange]
        
        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_3</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];
         D [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_4</TD>
                  <TD PORT="val">109</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];    
            
        Nil [shape=plaintext];

        A:next:c -> B:val;
        B:next:c -> B:val;
        C:next:c -> D:val;
        D:next:c -> Nil:w;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            head:p:s -> A;
        }
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            nodepp -> head;
        }
                {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=LR; 
            tmp:p:s -> A:next;
        }

}

好 ! 看的出來妳玩爆了這個串列。

先釐清其實 `tmp` 在這裡是用來防止 `node_1` 的位址遺失所以先指著，因為當`head` 改成指向 `node_2` 時 `node_1` 就遺失了，有點像上面` C = A ` 。

再來我們要想想真正要換的是什麼 ? ` A = node_1 next 所指向的位址 `、` B = node_2 next 所指向的位址 `

#### 2.
正確的程式碼:

*node = (*node)->next;
tmp->next = (*node)->next;
(*node)->next = tmp;

| Name | 記憶體位置 | 先前的Value | 執行完後的 value |
| ------------ | -------------- | -------------- |:---------------- |
| head | 0x7fff86ae7208 | 0x7fff86ae7240 | 0x7fff86ae7280 |
| .. | .. | .. | .. |
| nodepp | 0x7fff86ae721C | 0x7fff86ae7208 | 0x7fff86ae7208 |
| .. | .. | .. | .. |
| tmp | 0x7fff86ae7220 | 0x7fff86ae7240 | 0x7fff86ae7240 |
| .. | .. | .. | .. |
| node_1_value | 0x7fff86ae7240 | 72 | 72 |
| node_1_next | 0x7fff86ae7244 | 0x7fff86ae7280 | 0x7fff86ae72C8 |
| .. | .. | .. | .. |
| node_2_value | 0x7fff86ae7280 | 101 | 101 |
| .. | .. | .. | .. |
| node_2_next | 0x7fff86ae72C0 | 0x7fff86ae72C8 | 0x7fff86ae7240 |
| .. | .. | .. | .. |
| node_3_value | 0x7fff86ae72C8 | 108 | 108 |

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        nodepp[shape=plaintext,fontcolor=blue]
        tmp[shape=plaintext,fontcolor=orange]
        
        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_3</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];
         D [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_4</TD>
                  <TD PORT="val">109</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];    
            
        Nil [shape=plaintext];

        A:next:c -> C:val;
        B:next:c -> A:val;
        C:next:c -> D:val;
        D:next:c -> Nil:w;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            head:p:s -> B;
        }
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            nodepp -> head;
        }
                {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            tmp:p:s -> A;
        }

}

#### 3.(` node = &(*node)->next->next`、`node_t *tmp = *node;`)

node = &(*node)->next->next
* `node = 0x7fff86ae7244`(node_1_next 記憶體位置)

node_t *tmp = *node;
* `tmp = 0x7fff86ae72C8`(node_3_value 記憶體位置)

node_3_value 記憶體位置 = node_1_next 記憶體位置

| Name | 記憶體位置 | Value |
| ------------ | -------------- | -------------- |
| head | 0x7fff86ae7208 | 0x7fff86ae7280 |
| .. | .. | .. |
| nodepp | 0x7fff86ae721C | 0x7fff86ae7244 |
| .. | .. | .. |
| tmp | 0x7fff86ae7220 | 0x7fff86ae72C8 |
| .. | .. | .. |
| node_1_value | 0x7fff86ae7240 | 72 |
| node_1_next | 0x7fff86ae7244 | 0x7fff86ae72C8 |
| .. | .. | .. |
| node_2_value | 0x7fff86ae7280 | 101 |
| .. | .. | .. |
| node_2_next | 0x7fff86ae72C0 | 0x7fff86ae7240 |
| .. | .. | .. |
| node_3_value | 0x7fff86ae72C8 | 108 |
| node_3_next | 0x7fff86ae72CC | 0x7fff86ae72D0 |

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        nodepp[shape=plaintext,fontcolor=blue]
        tmp[shape=plaintext,fontcolor=orange]
        
        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_3</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];
         D [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_4</TD>
                  <TD PORT="val">109</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];    
            
        Nil [shape=plaintext];

        A:next:c -> C:val;
        B:next:c -> A:w;
        C:next:c -> D:val;
        D:next:c -> Nil:w;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            head:p:s -> B;
        }
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            nodepp -> A:next;
        }
                {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            tmp:p:s -> C;
        }

}

#### 4.(` swap 執行 `)
`node = 0x7fff86ae7244`(node_1_next 記憶體位置)
`tmp = 0x7fff86ae72C8`(node_3_value 記憶體位置)

`*node = (*node)->next;`
* `*node` 會是 `node_1_next` 的記憶體位置。
* `(*node)->next `會是 `node_3_next` 所指向的記憶體位置。
所以現在 `node_1_next` 的 value 被改成指向 `node_4`。

`tmp->next = (*node)->next;`
* `tmp->next` 所表示的是 `node_3_next`。
* `(*node)->next` 所表示的是 `Nil`。
所以現在 `node_3_next` 的 value 被改成指向 `Nil`。

`(*node)->next = tmp;`
所以現在 `node_4_next` 的 value 被改成指向 `node_3`。

| Name | 記憶體位置 | Value |
| ------------ | -------------- | -------------- |
| head | 0x7fff86ae7208 | 0x7fff86ae7280 |
| .. | .. | .. |
| nodepp | 0x7fff86ae721C | 0x7fff86ae7244 |
| .. | .. | .. |
| tmp | 0x7fff86ae7220 | 0x7fff86ae72C8 |
| .. | .. | .. |
| node_1_value | 0x7fff86ae7240 | 72 |
| node_1_next | 0x7fff86ae7244 | 0x7fff86ae72D0 |
| .. | .. | .. |
| node_2_value | 0x7fff86ae7280 | 101 |
| .. | .. | .. |
| node_2_next | 0x7fff86ae72C0 | 0x7fff86ae7240 |
| .. | .. | .. |
| node_3_value | 0x7fff86ae72C8 | 108 |
| node_3_next | 0x7fff86ae72CC | Nil |
| node_4_value | 0x7fff86ae72D0 | 109 |
| node_4_next | 0x7fff86ae72D4 | 0x7fff86ae72C8 |

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]

        head[shape=plaintext,fontcolor=red]
        nodepp[shape=plaintext,fontcolor=blue]
        tmp[shape=plaintext,fontcolor=orange]
        
        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="">node_1</TD>
                  <TD PORT="val">72</TD>
                  <TD PORT="next">   </TD>
              </TR>
            </TABLE>>];
        B [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_2</TD>
                  <TD PORT="val">101</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];

        C [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_3</TD>
                  <TD PORT="val">108</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];
         D [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR>
                  <TD PORT="val">node_4</TD>
                  <TD PORT="val">109</TD>
                  <TD PORT="next">    </TD>
              </TR>
            </TABLE>>];    
            
        Nil [shape=plaintext];

        A:next:c -> D:val;
        B:next:c -> A:w;
        C:next:c -> Nil:w;
        D:next:c -> C:val;
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            head:p:s -> B;
        }
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            nodepp -> A:next;
        }
                {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
            tmp:p:s -> C;
        }

}

不覺得那個 node 指標很熟悉嗎? 沒錯它就是 pointer to pointer，所以 swap_pair() 也可以用 pointer to pointer 來實現。
### swap_pair() 的 pointer to pointer 版本

void swap_pair(node_t **head)
{
    node_t *tmp = NULL;
    for(; *head && (*head)->next; head = &(*head)->next->next ){
        tmp = *head;
        *head = (*head)->next;
        tmp->next = (*head)->next;
        (*head)->next = tmp;
    }
}

## reverse()

node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next;
        CCC;
        head = next;
    }
    return cursor;
}

### `CCC`
- [ ] `(a)` `cursor = head; head->next = cursor`
- [x] `(b)` `head->next = cursor; cursor = head`
- [ ] `(c)` `cursor = head`
- [ ] `(d)` `head->next = cursor`
- [ ] `(e)` `head->next->next = cursor; cursor->next = head`
- [ ] `(f)` `cursor->next = head; head->next->next = cursor`

### 解題思路
先思考如果只有兩個指標這件事情可以嗎？

1.

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>>];

        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; head:p:s -> a:val;
        }
        
        {
            rank=same; next:p:s -> b:val;
        }
}

當我們做完 `node1` & `node2`的反轉
2.

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>>];

        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>>];
            
        next [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
              <TR><TD PORT="p">next</TD></TR>
            </TABLE>>];
            
        null [label=<
            <TABLE BORDER="0" CELLBORDER="0" cellspacing="0">
              <TR><TD PORT="p">NULL</TD></TR>
            </TABLE>>]; 
            
        null:p:e -> a:next:c [dir=back];
        a:next:c -> b:val [style=invis];
        a:e -> b:next:c [dir=back];
        b:next:c -> c:val [style=invis];
        c:next:c -> d:val;
        
        {
            rank=same; head:p:s -> a:val;
        }
        
        {
            rank=same; next:p:s -> b:val;
        }
}

做到這裡我們可以發現我們遺失了 node3 的實體位址，所以這樣是不行的！

1. 所以我們需要加入 `cursor` 來 keep 住前面的點，並且利用 `next` 來防止下一個要做反轉的 `node` 遺失位址。

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;
        }
}

2. 這邊顯示了做了一次後指標所指向的位址，可以看到 cursor 把持住了 node1 位址可以拿來防止遺失，所以我們才會做 `cursor = head ` 來 keep 住每次做反轉 next 的 node，並且由 `head = next;` 來去指向下一個要做的點。

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 -> a:val;
        }
        
        {
            rank=same; head:p:s -> b:val;
        }
        
        {
            rank=same; next:p:s -> b:val;
        }
}