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

###### tags: `linux2020`

## 程式運作原理

### swap_pair

node_t *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;
    }
    return head;
}

1. 一開始會有一個 `node` 為 pointer to pointer，然後 for 會判斷說這一個跟下一個是不是 NULL，不是的話就可以做 swap，每一次做完就讓 node 往後指兩個。
2. 先用一個 tmp 指向 *node 指的地方

digraph linked_list{
    rankdir = LR;
    node [shape = record];
    subgraph cluster_0 {
        style = "filled";
        color = "black";
        fillcolor = "lightyellow";
		node [style = filled, fillcolor = white, color = black];
        label = "pointer to pointer";
        node_;
    };
    subgraph cluster_1 {
        style = "filled";
        color = "black";
        fillcolor = "lightyellow";
		node [style = filled, fillcolor = white, color = black];
        label = "list";
        a;
        b;
        c;
        d;
    };
    node_ -> a;
    a -> b -> c -> d;
    tmp -> a
}

3. 將 *node 指向 *node->next

digraph linked_list{
    rankdir = LR;
    node [shape = record];
    subgraph cluster_0 {
        style = "filled";
        color = "black";
        fillcolor = "lightyellow";
		node [style = filled, fillcolor = white, color = black];
        label = "pointer to pointer";
        node_;
    };
    subgraph cluster_1 {
        style = "filled";
        color = "black";
        fillcolor = "lightyellow";
		node [style = filled, fillcolor = white, color = black];
        label = "list";
        a;
        b;
        c;
        d;
    };
    node_ -> b;
    a -> b -> c -> d;
    tmp -> a
}

4. 將 tmp->next 接上 (*node)->next

digraph linked_list{
    rankdir = LR;
    node [shape = record];
    subgraph cluster_0 {
        style = "filled";
        color = "black";
        fillcolor = "lightyellow";
		node [style = filled, fillcolor = white, color = black];
        label = "pointer to pointer";
        node_;
    };
    subgraph cluster_1 {
        style = "filled";
        color = "black";
        fillcolor = "lightyellow";
		node [style = filled, fillcolor = white, color = black];
        a;
        b;
        c;
        d;
    };
    node_ -> b;
    b -> c -> d;
    a -> c;
    tmp -> a;
}

5. 最後再把 (*node)->next 往前接回 tmp

digraph linked_list{
    rankdir = LR;
    node [shape = record];
    subgraph cluster_0 {
        style = "filled";
        color = "black";
        fillcolor = "lightyellow";
		node [style = filled, fillcolor = white, color = black];
        label = "pointer to pointer";
        node_;
    };
    subgraph cluster_1 {
        style = "filled";
        color = "black";
        fillcolor = "lightyellow";
		node [style = filled, fillcolor = white, color = black];
        a;
        b;
        c;
        d;
    };
    node_ -> b;
    c -> d;
    a -> c;
    b -> a;
    tmp -> a;
}

6. 讓 `node` 往後指到下兩個，node = &(*node)->next->next

digraph linked_list{
    rankdir = LR;
    node [shape = record];
    subgraph cluster_0 {
        style = "filled";
        color = "black";
        fillcolor = "lightyellow";
		node [style = filled, fillcolor = white, color = black];
        label = "pointer to pointer";
        node_;
    };
    subgraph cluster_1 {
        style = "filled";
        color = "black";
        fillcolor = "lightyellow";
		node [style = filled, fillcolor = white, color = black];
        a;
        b;
        c;
        d;
    };
    node_ -> c;
    c -> d;
    a -> c;
    b -> a;
    tmp -> a;
}

## 更改為 pointer to pointer

### swap_pair
將 `head` 直接取代掉原本的 `node`，因為 `node` 做的事情就是一直去找後兩個 pointer，所以當我傳 pointer to pointer 的 `head` 時，就可以用他來達成這項功能

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

### reverse
將最後的 `head` 重新指向 `cursor` 指的地方就好了，因為照著原本的邏輯跑，`cursor` 在最後會指向一開始的尾巴，也就是 reverse 過後新的起點，而 `head` 則會跑去指向 `NULL`，這時候只要把 `head` 拉過去指向新的起點就可以了

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

## 更改 reverse 為 recursive version
目前是做出最直觀的寫法，就是直接把原本 iterate 的版本套下去改成遞迴，還在思索有沒有更好的寫法，因為一直 call function 成本不低

void rev_recursive(node_t **head, node_t *cursor){
    if(*head){
        node_t *next = (*head)->next;
        (*head)->next = cursor; 
        cursor = *head;
        *head = next;
        rev_recursive(head, cursor);
    }else{
        *head = cursor;
    }
}

void reverse(node_t **head)
{
    rev_recursive(head, NULL);    
}

## Fisher–Yates shuffle

### Modern method
先計算出 `size`，直觀的從大到小跑迴圈，在每一次的範圍內做 random，並且將得到的數字按照順序跟 size~1 的值做交換
因為交換的順序是從最後面到前面，不斷的交換數值，比起 array 用 singly-linked list 不是很有效率，但目前還沒想到解法

void shuffle(node_t *head)
{
    srand(time(NULL));
    int size = 0;
    for(node_t *tmp = head; tmp!=NULL; tmp=tmp->next)
        size++;
    for(int i=size; i>1; i--){
        int num = rand() % i;
        node_t *tmpA = head, *tmpB = head;
        for(int j=0; j<num; ++j)
            tmpA = tmpA->next;
        for(int j=0; j<i-1; ++j)
            tmpB = tmpB->next;
        
        int val = tmpA->value;
        tmpA->value = tmpB->value;
        tmpB->value = val;
    }
}