# 2020q3 Homework1 (quiz1)
contributed by< `JimmyLiu0530` >

###### tags: `進階電腦系統理論與實作`

- [Linked list 測驗題目](https://hackmd.io/@sysprog/sysprog2020-quiz1)

## 測驗1: singly linked list
題目給定 linked list 結構定義為:

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

且已知不存在 circular (環狀結構) 情況下，對單向 linked list 進行操作

圖例:

digraph foo{
    rankdir=LR;
        node [shape=record];
        a [label="{ <data> 12 | <ref>  }"]
        b [label="{ <data> 54 | <ref>  }"];
        c [label="{ <data> 37 | <ref>  }"];
        
        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 -> NULL      [arrowhead=vee, arrowtail=dot,             dir=both, tailclip=false];
}

### 原始測驗題的思考及理解
- `add_entry`
> 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy

程式碼如下:

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

#### 核心觀念: 找到整串 linked list 的尾巴，將它指向新增的節點
運作原理如下:
1. **第3行** 建立一個指向 head 的指標 indirect ( pointer to pointer )

graph LR
    subgraph linked list
        head==>node1==>node2
    end
    subgraph pointer to pointer
        indirect==>head
    end

2. **第5-7行** 配置一個 node_t 的空間，並初始化
3. **第9行** 應選 `assert(new_node)`，用來檢查new_node是否合法
4. **第10-11行** 用來找到 linked list 的最後一個 node。下圖展示第一圈 while 後的結果，以此類推

graph LR
    subgraph linked list
        head==>node1==>node2
    end
    subgraph pointer to pointer
        indirect==>node1
    end

5. **第12行** 應選***indirect = new_node**，把最後一個 node 的 next 指向 new_node，增加節點完成

:::warning
**Note**
- `->` 的執行順位大於 `&` ，所以要先進行 `->` 運算再運算 `&`
:::

- `remove_entry`
> 移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)

程式碼如下:

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

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

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

#### 核心觀念: 繞過欲刪除的節點

運作原理如下:
1. **第3行** 建立一個指向 head 的指標 indirect ( pointer to pointer )

graph LR
    subgraph linked list
        head==>node1==>entry==>node3
    end
    subgraph pointer to pointer
        indirect==>head
    end

2. **第5-6行** 找到欲刪除的節點 entry

graph LR
    subgraph linked list
        head==>node1==>entry==>node3
    end
    subgraph pointer to pointer
        indirect==>node1
    end

3. **第8行** 繞過 entry，也就是說把 entry 的上一個節點改指向 entry 的下一個節點

graph LR
    subgraph linked list
        head==>node1==>node3
        entry==>node3
    end
    subgraph pointer to pointer
        indirect==>node1
    end

4. **第9行** 釋放 entry 的記憶體資源

graph LR
    subgraph linked list
        head==>node1==>node3
    end
    subgraph pointer to pointer
        indirect==>node1
    end

- `swap_pair`
> 交換一對相鄰的節點，取自 [LeetCode: Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)，給定 `1->2->3->4`，則該回傳 `2->1->4->3`

程式碼如下:

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

#### 核心觀念: 倆倆一組，相關指標做改變

運作原理如下:
1. **第3行 for 條件** 應選 `node = &(*node)->next->next`，因為此 function 為兩兩交換，因此下一輪 node pointer 應指向目前這對的尾，如下所示:

graph LR
    subgraph linked list
        head==>node1==>node2==>node3==>node4
    end
    subgraph pointer to pointer
        node==>node2
    end

2. **第4行** 建立一個 tmp 指向該對的頭，如下所示:

graph LR
    subgraph linked list
        head==>node1==>node2==>node3==>node4
    end
    subgraph pointer to pointer
        node==>head
    end
    subgraph temp
        tmp==>node1
    end

3. **第5行** 應選 `*node = (*node)->next`，使 head 改指向該對的尾(e.g. node2)，如下所示:

graph LR
    subgraph linked list
        head==>node2
        node1==>node2==>node3==>node4
    end
    subgraph pointer to pointer
        node==>head
    end
    subgraph temp
        tmp==>node1
    end

4. **第6行** 該對的頭 (e.g. node1) 的 next 改指向下一對的頭 (e.g. node3)，如下所示:

graph LR
    subgraph linked list
        head==>node2
        node1==>node3
        node2==>node3==>node4
    end
    subgraph pointer to pointer
        node==>head
    end
    subgraph temp
        tmp==>node1
    end

5. **第7行** 該對的尾 (e.g. node2) 的 next 改指向頭 (e.g. node1)，如下所示:

graph LR
    subgraph linked list
        head==>node2
        node1==>node3
        node2==>node1
        node3==>node4
    end
    subgraph pointer to pointer
        node==>head
    end
    subgraph temp
        tmp==>node1
    end

6. 之後依此類推...直到交換結束，或是只剩沒成對的node。最後 return 交換後整個 linked list 的頭

- `reverse`
> 將給定的 linked list 其內節點予以反向，即 `1->2->3->4`，則該回傳 `4->3->2->1`

程式碼如下:

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

#### 核心觀念: 將 cursor 視為指向 head 的前一個節點，next 視為指向 head 的後一個節點。不斷更新(往後挪)三個指標 cursor、head、next直到 linked list 的尾巴

運作原理如下:
1. **第5行** 創建一個指標 next 指向目前 head 所指的節點的下一個節點。如圖 next 指向 node2

graph LR
    subgraph linked list
        head==>node1==>node2==>node3==>node4
        next==>node2
        cursor==>NULL
    end

2. **第6行** 應選 `head->next = cursor; cursor = head` ，如圖先將 head->next (i.e. node1) 指向 cursor 指的 NULL，再將 cursor 指向 head

graph LR
    subgraph linked list
        head==>node1
        cursor==>node1
        next==>node2==>node3==>node4
        node1==>NULL
    end

3. **第7行** 將 head 指標往後挪一個節點，如圖 head 從指向 node1 變成 node2

graph LR
    subgraph linked list
        head==>node2
        cursor==>node1
        next==>node2==>node3==>node4
        node1==>NULL
    end

### 延伸問題
#### 1.避免回傳指標的函式 `swap_pair_revised` & `reverse_revised`
說明: 利用指標的指標對 `swap_pair` 及 `reverse` 兩函式做改寫，來達到不需回傳整串 linked list 的 head

- `swap_pair_revised`

程式碼如下:

void swap_pair_revised(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;
    }
}

主程式呼叫:
`swap_pair_revised(&head);`

運作原理如下:
1. 與函式 `swap_pair` 只有傳入 parameter 的方式不同，差別在於 `swap_pair` 採 **pass by value** 的方法；而 `swap_pair_revised` 則是採 **pass by reference** 的方法。有關 pass by value 跟 reference 的詳細解說，可到 [Pass by value vs Pass by reference](https://medium.com/@racktar7743/c-c-%E6%8C%87%E6%A8%99%E6%95%99%E5%AD%B8-%E5%9B%9B-pass-by-value-vs-pass-by-reference-ed5882802789) 觀看

- `reverse_revised`

程式碼如下:

void reverse_revised(node_t **indirect)
{
    node_t *cursor = NULL;
    while (*indirect) {
        node_t *next = (*indirect)->next;
        (*indirect)->next = cursor;
        cursor = *indirect;
        *indirect = next;
    }
    *indirect = cursor;
}

主程式呼叫:
`reverse_revised(&head);`

運作原理如下:
1. 與原函式概念一樣，只是改採用 pass by reference 的方法，因此一些相對應的變數(e.g. while 的條件從 `head` 改成 `*indirect`)也須做修改
2. **第10行** 最後再把新的 linked list 頭的位置 assign 到 head (i.e. *indirect) 去

#### 2. 以遞迴改寫 `reverse` 函式

首先，建立**遞迴**演算法有幾個重點: (a) **終止條件** (b) **將原問題變成與其相似且規模較小的問題**

程式碼如下:

node_t *rev_recursive(node_t *p)
{
    if(p->next == NULL)
    {
        return p; 
    }
    node_t *head = rev_recursive(p->next);
    node_t *q = p->next;
    q->next = p;
    p->next = NULL;
    return head;
}

主程式呼叫:
`head = rev_recursive(head);`

運作原理如下:
1. **第3-6行** 即為終止條件。if 條件若成立，代表 p 為此 linked list 的最後一個節點，也就是新的 head，因此回傳該位址
2. **第7行** 遞迴呼叫 rev_recursive()，並將新的 head 記錄下來
3. **第8-10行** 舉例來說，假設 p 指向 node2，則 q 指向 node3。經過這幾行的處理後，第一張圖會變成第二張圖，也就是 node3->next 指向 node2，且 node2->next 指向 NULL

graph LR
    subgraph linked list
        head==>node1==>node2==>node3==>NULL
    end

graph LR
    subgraph linked list
        head==>node1==>node2==>NULL
        node3==>node2
    end

#### 3. 針對 singly-linked list 的節點，實作 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)，儘量降低記憶體的使用量

什麼是 `Fisher–Yates shuffle`?
> 用來將一個有限集合生成一個隨機排列的方法，簡單來說，該算法可以洗牌序列。該算法產生無偏頗的排列，代表每種排列的可能性均等。

程式碼如下

// this swap function is under the premise that
// 1 <= p <= q <= total number of node in the linked list
// and is used to swap pth and qth node in the linked list

void swap(node_t **head, int p, int q)
{
    // nothing to do if p,q are the same
    if(p == q)
        return;
    
    // search for pth node in the linked list
    node_t *prevP = NULL, *currP = *head;
    for(int i = p-1; i>0; i--)
    {
        prevP = currP;
        currP = currP->next;
    }
    
    // search for qth node in the linked list
    node_t *prevQ = NULL, *currQ = *head;
    for(int i = q-1; i>0; i--)
    {
        prevQ = currQ;
        currQ = currQ->next;
    }
    // if pth node is head of linked list, i.e. p==1, make qth node a new head
    if (p==1)
        *head = currQ;
    else
        prevP->next = currQ;
    
    // if q is 1, p must be 1 either, the process will return due to line7
    prevQ->next = currP;
    
    // swap next pointers
    node_t *tmp = currQ->next;
    currQ->next = currP->next;
    currP->next = tmp;
}

void Fisher_Yates_shuffle(node_t **indirect)
{
    // count how many nodes are in linked list
    int totalNum = 0;
    node_t *tmp = *indirect;
    while(tmp)
    {
        totalNum += 1;
        tmp = tmp->next;
    }
    
    srand(time(NULL));
    
    // start from the first node and randomly choose a number q s.t. p<=q<=totalNum 
    for(int p = 1; p <= totalNum-1; p++)
    {
        int q = (rand() % (totalNum-p+1))+p;
        
        swap(indirect, p, q);
    }   
}

主程式呼叫:
`Fisher_Yates_shuffle(&head);`

運作原理如下:
1. 先說明 `swap` 函式，主要將第 p 跟第 q 個節點交換
**第11-24行** 先找到第 p 跟第 q 個節點的位置，並記錄在 currP 及 currQ， prevP 跟 prevQ 則分別記錄 currP 及 currQ 的前一個節點

**第26-27行** 需考慮 p==1 的情況，也就是第 p 個節點是 head

**第33行** 之所以這裡不用 if-else 是因為在給定的前提中，1 <= p <= q。當 q=1 時，
p 勢必也是 1 ，因此會在 `line 8` retrun 掉了

**第36-38行** 做一些 `next` pointer 的交換
2. 此 `swap` 函式因為是 linked list，所以不像 array 在給定第 p 跟第 q 個元素做交換下可在O(1)完成，需 $O(n)$。

3. 接著看 `Fisher_Yates_shuffle` 函式，此函式精神在於在第 p 輪中，會隨機找一個介於 p 跟總節點數的數字 q，並將第 p 跟第 q 個交換
**第44-50行** 計算 linked list 的總節點數
**第55-60行** 從 linked list 的第一個節點開始，在之間隨機找一個節點做交換，再來換第二個節點...以此類推，一直重複做到倒數第二個節點
4. 此`Fisher_Yates_shuffle` 函式的時間複雜度為 $O(n^2)$，但空間複雜度只需 $O(1)$。