# 2020q3 Homework1 (quiz1)
contributed by guaneec

###### tags: `sysprog2020`

## Q1 - Linked list

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

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

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;
    assert(new_node);
    while (*indirect)
        indirect = &(*indirect)->next;
    // AA2;
    *indirect = new_node;
}

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

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

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

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

node_t *swap_pair(node_t *head)
{
    for (node_t **node = &head; *node && (*node)->next; /* BB1 */
         node = &(*node)->next->next) {
        node_t *tmp = *node;
        /* BB2  */
        *node = (*node)->next;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
    return head;
}

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

        head = next;
    }
    return cursor;
}

void print_list(node_t *head)
{
    for (node_t *current = head; current; current = current->next)
        printf("%d ", current->value);
    printf("\n");
}

int main(int argc, char const *argv[])
{
    node_t *head = NULL;

    print_list(head);

    add_entry(&head, 72);
    add_entry(&head, 101);
    add_entry(&head, 108);
    add_entry(&head, 109);
    add_entry(&head, 110);
    add_entry(&head, 111);

    print_list(head);

    node_t *entry = find_entry(head, 101);
    remove_entry(&head, entry);

    entry = find_entry(head, 111);
    remove_entry(&head, entry);

    print_list(head);

    /* swap pair.
     * See https://leetcode.com/problems/swap-nodes-in-pairs/
     */
    head = swap_pair(head);
    print_list(head);

    head = reverse(head);
    print_list(head);

    return 0;
}

### Q1.1 - Explanation
### Q1.2 - Change function signature
Make `swap_pair` and `reverse` return void instead
[Diff](https://github.com/guaneec/sysprog-2020q3-quiz1/commit/cd9470d59fbbc3013585af7a4608106197a6628d)
### Q1.3 - Recursive reverse

void reverse(node_t **head)
{
    if (!*head)
        return;
    node_t *tmp = (*head)->next;
    if (!tmp) return;
    reverse(&(*head)->next);
    tmp->next = (*head);
    tmp = (*head)->next;
    (*head)->next = NULL;
    *head = tmp;
}

### Q1.4 - Fisher-Yates shuffle

int length(node_t *head) {
    int l = 0;
    for (; head; head = head->next) ++l;
    return l;
}

void shuffle(node_t **head)  {
    node_t tmpheadnew;
    node_t tmpheadold = {.next = *head};
    node_t *tail = &tmpheadnew;
    for (int l = length(*head); l > 0; --l) {
        // pick a random remaining node
        int r = rand() % l;
        node_t *cursor = &tmpheadold;
        for (int i = 0; i < r; ++i) {
            cursor = cursor->next;
        }

        // append node to new list and remove from old list
        tail->next = cursor->next;
        tail = tail->next;
        cursor->next = cursor->next->next;
    }
    *head = tmpheadnew.next;
}