---
# System prepended metadata

title: 2020q3 Homework (quiz1)
tags: [sysprog2020]

---

# 2020q3 Homework (quiz1)
contributed by < `nickchenchj` >
###### tags: `sysprog2020`

## Prerequisite
* [problems for quiz1 (2020q3)](https://hackmd.io/@sysprog/sysprog2020-quiz1)

## Explanation
###### Note: all codes below are written in C language, and they can be found in my [GitHub repository](https://github.com/nickchenchj/Computer-Systems)

### Structure of Singly Linked List (SLL)
To define the structure of singly linked list (SLL), **`struct`** statement is required. The structure of SLL is represented as:
```c
typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;
```
* schematic representation of SLL:
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    head [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> value1 | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> value2 | <next> }"
    ]
    NULL [shape=plaintext]
    
    head -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> NULL [tailclip=false]
}
```
###### Note: no circular SLL exist

### Basic Operations on SLL
* **`add_entry`**: appends a new node to the list
* **`find_entry`**: finds a specific node and returns its address
* **`remove_entry`**: removes a specific node and frees its memory by using `pointer to pointer`
* **`swap_pair`**: swaps nodes in pairs (e.g. {1, 2, 3, 4} => {2, 1, 4, 3}; For more information, see [LeetCode: Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/))
* **`reverse`**: reverses the given list by using `rev_recursive` (e.g. {1, 2, 3, 4} => {4, 3, 2, 1})
    * **`rev_recursive`:** reverses the given list recursively
* **`print_list`**: prints all the nodes in the list


### Solutions to AA1 and AA2
* code snippet of `add_entry`:
```c=
/* Appends a new node to the list */
void add_entry(node_t **head, int new_value)
{
    /* Creates a pointer to pointer called `indirect` 
     * and makes it point to the address of `head` 
     * in the list */
    node_t **indirect = head;

    node_t *new_node = malloc(sizeof(node_t));

    AA1;
    new_node->value = new_value;
    new_node->next = NULL;

    /* (*indirect) is the value (address of a node) 
     * of the pointer that indirect points to */
    while (*indirect)
        /* indirect points to the pointer 
         * which points to the next node */
        indirect = &(*indirect)->next;
    AA2;
}
```
#### AA1 = ?
* `(a)` `assert(new_node)`
* `(b)` `*indirect = new_node`

:::info
**Idea**
Remember, always make sure that memory allocation is successful before changing the values of the new node (`NULL` will be returned if memory allocation fails). To prevent dereferencing null pointers, `assert(new_node)` will be an ideal choice of this problem.
:::

:::success
Answer: `(a)` `assert(new_node)`
:::

#### AA2 = ?
* `(a)` `assert(new_node)`
* `(b)` `*indirect = new_node`

:::info
**Idea**
1. Find the last node.
2. Append a new node to the end of the list.
:::

#### Implementation
1. Store the address of `head` into `indirect`:
```graphviz
digraph add_entry{
    rankdir=LR
    node [shape=record]

    indirect [
        label="indirect"
        shape=plaintext
        fontcolor=red
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    indirect -> head:address [color=red]
    head -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> NULL [tailclip=false]
} 
```
2. Let `indirect` store the address of `*indirect->next` until `*indirect` == `NULL`:

* **After the 1st iteration:**
```graphviz
digraph add_entry{
    rankdir=LR
    node [shape=record]

    indirect [
        label="indirect"
        shape=plaintext
        fontcolor=red
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    indirect -> node1:next [color=red]
    head -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> NULL [tailclip=false]
} 
```

* **After the 2nd iteration:**
```graphviz
digraph add_entry{
    rankdir=LR
    node [shape=record]

    indirect [
        label="indirect"
        shape=plaintext
        fontcolor=red
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    indirect -> node2:next [color=red]
    head -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> NULL [tailclip=false]
} 
```
3. After the second iteration, we can see that `indirect` points to `next` of the last node in the list (`node2` in this case), and it also matches the exit condition of the while loop (`*indirect` == `NULL`).
4. To append `new_node` to the list, we assign `new_node` to `*indirect`. So option `(b)` `*indirect = new_node` is the correct answer.
* **Before:**
```graphviz
digraph add_entry{
    rankdir=LR
    node [shape=record]

    indirect [
        label="indirect"
        shape=plaintext
        fontcolor=red
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> *indirect == NULL }"
    ]
    new_node [
        xlabel="*(new_node)"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    indirect -> node2:next [color=red]
    head -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next -> NULL [tailclip=false]
    new_node:next:c -> NULL [tailclip=false]
} 
```
* **After:**
```graphviz
digraph add_entry{
    rankdir=LR
    node [shape=record]

    indirect [
        label="indirect"
        shape=plaintext
        fontcolor=red
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> *indirect == new_node }"
    ]
    new_node [
        xlabel="*(new_node)"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    indirect -> node2:next [color=red]
    head -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next -> new_node [tailclip=false]
    new_node:next:c -> NULL [tailclip=false]
} 
```
:::success
Answer: `(b)` `*indirect = new_node`
:::

---

### Solutions to BB1 and BB2
* code snippet of `swap_pair`:
```c=
/* Swaps nodes in pairs 
 * e.g. {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;
}
```

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

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


:::info
**Idea**
1. We need a **cursor** with the type of `node_t**` to indicate the first node pair that we haven't swapped.
2. A temporary variable with the type of `node_t*` is required, and it is used for storing the address of one of the two nodes when swapping nodes in pairs.
:::

* pseudocode (single iteration):
```c=
BB2; /* points to the second node of the node pair */
tmp->next = (*node)->next; /* points to the first node of the "next" node pair */
(*node)->next = tmp; /* tmp points to the first node of the node pair */
BB1; /* lets node be able to find the first node of the "next" pair */
```

#### Implementation
1. Create a cursor (`node`) and a temporary variable (`tmp`):
```c
node_t **node = &head; /* line 5 */
node_t *tmp = *node;   /* line 6 */
```
```graphviz
digraph swap_pair{
    rankdir=LR
    node [shape=record]

    cursor [
        label="node"
        shape=plaintext
        fontcolor=red
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    tmp [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> head [color=red]
    head -> node1 [color=blue]
    tmp -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```
2. Swap `node1` and `node2`:
* **BB2:** Point to the second node in the node pair.
```c
*node = (*node)->next; /* option (c) */
```
```graphviz
digraph swap_pair{
    rankdir=LR
    node [shape=record]

    cursor [
        label="node"
        shape=plaintext
        fontcolor=red
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    tmp [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> head [color=red]
    head -> node2 [color=blue]
    tmp -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```
* Point to the first node in the **next** node pair.
```c
tmp->next = (*node)->next; /* line 8 */
```
```graphviz
digraph swap_pair{
    rankdir=LR
    node [shape=record]

    cursor [
        label="node"
        shape=plaintext
        fontcolor=red
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    tmp [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> head [color=red]
    head -> node2 [color=blue]
    tmp -> node1 [color=blue]
    node1:next:c -> node3 [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```
* Let `node2` point to `node1`.
```c
(*node)->next = tmp; /* line 9 */
```
```graphviz
digraph swap_pair{
    rankdir=LR
    node [shape=record]

    cursor [
        label="node"
        shape=plaintext
        fontcolor=red
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    tmp [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> head [color=red]
    head -> node2 [color=blue]
    tmp -> node1 [color=blue]
    node1:next:c -> node3 [tailclip=false]
    node2:next:c -> node1 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```
3. **BB1:** Let `node` points to `node1.next`, which is the address of the first node in the next pair (`node3` in this case).

* `&node1.next`
=> `&node2.next->next`
=> `&head->next->next`
=> `&(*node)->next->next`

```c
node = &(*node)->next->next; /* option (e) */
```
```graphviz
digraph swap_pair{
    rankdir=LR
    node [shape=record]

    cursor [
        label="node"
        shape=plaintext
        fontcolor=red
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    tmp [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> node1:next [color=red]
    head -> node2 [color=blue]
    tmp -> node1 [color=blue]
    node1:next:c -> node3 [tailclip=false]
    node2:next:c -> node1 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```
4. Repeat step 2 until all pairs are swapped.
5. Return the new `head`.
6. Done!

:::success
**Answer**
BB1: `(e)` `node = &(*node)->next->next`
BB2: `(c)` `*node = (*node)->next`
:::

---

### Solution to CCC
* code snippet of `reverse`:
```c=
/* Reverses the given list 
 * e.g. {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;
}
```

* **Before `reverse`:**
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    head [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    head -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```

* **After `reverse`:**
```graphviz
digraph reverse{
    rankdir=RL
    node [shape=record]

    head [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    head -> node3 [color=blue]
    node1:next:c -> NULL [tailclip=false]
    node2:next:c -> node1 [tailclip=false]
    node3:next:c -> node2 [tailclip=false]
} 
```

#### CCC = ?
* `(a)` `cursor = head; head->next = cursor`
* `(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`

:::info
**Idea**
1. Create a `cursor` that points to the previous node (points to `NULL` if the current node is the first node in the list).
2. Create a pointer called `next` that points to the next node (points to `NULL` if the current node is the last node in the list).
3. Let the current node point to the address that `cursor` points to.
4. Let `cursor` point to the current node.
5. Let `head` point to the next node.
:::

#### Implementation
1. Create a `cursor` that stores `NULL` first, and stores the address of the previous node in the following iterations:
```c
node_t *cursor = NULL;
```
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        shape=plaintext
        fontcolor=blue
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> NULL [color=blue]
    head -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```

2. Create a pointer called `next` that points to the next node (points to `NULL` if the current node is the last node in the list):

| current node | next node |
|:------------:|:---------:|
|   `node1`    |  `node2`  |


```clike
node_t *next = head->next;
```
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        shape=plaintext
        fontcolor=blue
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    next [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> NULL [color=blue]
    head -> node1 [color=blue]
    next -> node2 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```

3. **CCC:**
* Let the current node point to the address that `cursor` points to:
```clike
head->next = cursor; /* CCC part1 */
```
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        shape=plaintext
        fontcolor=blue
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    next [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> NULL [color=blue]
    head -> node1 [color=blue]
    next -> node2 [color=blue]
    node1:next:c -> NULL [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```

* Let `cursor` point to the current node:
```clike
cursor = head; /* CCC part2 */
```
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        shape=plaintext
        fontcolor=blue
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    next [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> node1 [color=blue]
    head -> node1 [color=blue]
    next -> node2 [color=blue]
    node1:next:c -> NULL [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```

4. Let `head` point to the next node:
```clike
head = next;
```
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        shape=plaintext
        fontcolor=blue
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    next [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> node1 [color=blue]
    head -> node2 [color=blue]
    next -> node2 [color=blue]
    node1:next:c -> NULL [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```

5. Repeat **Step 2 ~ Step 4**:

| current node | next node |
|:------------:|:---------:|
|   `node2`    |  `node3`  |

* Let `next` point to the next node:
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        shape=plaintext
        fontcolor=blue
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    next [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> node1 [color=blue]
    head -> node2 [color=blue]
    next -> node3 [color=blue]
    node1:next:c -> NULL [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```

* Let the current node point to the address that `cursor` points to (`node1` in this case):
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        shape=plaintext
        fontcolor=blue
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    next [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> node1 [color=blue]
    head -> node2 [color=blue]
    next -> node3 [color=blue]
    node1:next:c -> NULL [tailclip=false]
    node2:next:c -> node1 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```

* Let `cursor` point to the current node:
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        shape=plaintext
        fontcolor=blue
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    next [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> node2 [color=blue]
    head -> node2 [color=blue]
    next -> node3 [color=blue]
    node1:next:c -> NULL [tailclip=false]
    node2:next:c -> node1 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```

* Let `head` point to the next node:
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        shape=plaintext
        fontcolor=blue
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    next [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> node2 [color=blue]
    head -> node3 [color=blue]
    next -> node3 [color=blue]
    node1:next:c -> NULL [tailclip=false]
    node2:next:c -> node1 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```

6. Repeat **Step 2 ~ Step 4**:

| current node | next node |
|:------------:|:---------:|
|   `node3`    |  `NULL`   |

* Let `next` point to the next node (`NULL` in this case):
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        shape=plaintext
        fontcolor=blue
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    next [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> node2 [color=blue]
    head -> node3 [color=blue]
    next -> NULL [color=blue]
    node1:next:c -> NULL [tailclip=false]
    node2:next:c -> node1 [tailclip=false]
    node3:next:c -> NULL [tailclip=false]
} 
```

* Let the current node point to the address that `cursor` points to (`node2` in this case):
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        shape=plaintext
        fontcolor=blue
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    next [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> node2 [color=blue]
    head -> node3 [color=blue]
    next -> NULL [color=blue]
    node1:next:c -> NULL [tailclip=false]
    node2:next:c -> node1 [tailclip=false]
    node3:next:c -> node2 [tailclip=false]
} 
```

* Let cursor point to the current node (`node3`):
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        shape=plaintext
        fontcolor=blue
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    next [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> node3 [color=blue]
    head -> node3 [color=blue]
    next -> NULL [color=blue]
    node1:next:c -> NULL [tailclip=false]
    node2:next:c -> node1 [tailclip=false]
    node3:next:c -> node2 [tailclip=false]
} 
```

* Let `head` point to the next node (`NULL`):
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        shape=plaintext
        fontcolor=blue
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    next [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> node3 [color=blue]
    head -> NULL [color=blue]
    next -> NULL [color=blue]
    node1:next:c -> NULL [tailclip=false]
    node2:next:c -> node1 [tailclip=false]
    node3:next:c -> node2 [tailclip=false]
} 
```

7. Return `cursor` as the new `head`:
```graphviz
digraph reverse{
    rankdir=LR
    node [shape=record]

    cursor [
        label="cursor\n(new head)"
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        xlabel="node1"
        label="{ <value> | <next> }"
    ]
    node2 [
        xlabel="node2"
        label="{ <value> | <next> }"
    ]
    node3 [
        xlabel="node3"
        label="{ <value> | <next> }"
    ]
    NULL [shape=plaintext]

    cursor -> node3 [color=blue]
    node1:next:c -> NULL [tailclip=false]
    node2:next:c -> node1 [tailclip=false]
    node3:next:c -> node2 [tailclip=false]
} 
```

8. Done!

:::    success
Answer: `(b)` `head->next = cursor; cursor = head`
:::

---

### Side Questions
1. Explain how other SLL operations work:
* **`find_entry`**: finds a specific node and returns its address
```c=
node_t *find_entry(node_t *head, int value)
{
    node_t *current = head;
    for (; current && current->value != value; current = current->next)
        /* iterate */;
    return current;
}
```

* **`remove_entry`**: removes a specific node and frees its memory by using pointer to a pointer
```c=
void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

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

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

* **`print_list`**: prints all the nodes in the list
```c=
void print_list(node_t *head)
{
    for (node_t *current = head; current; current = current->next)
        printf("%d ", current->value);
    printf("\n");
}
```

2. Change the return type of `swap_pair` and `reverse` from `node_t*` to `void`:
* **`swap_pair`**
```c=
/* Before */
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;
}

int main() {
    ...
    head = swap_pair(head);
    ...
}
```
```c=
/* After */
void swap_pair(node_t **indirect)
{
    for (node_t **node = indirect; *node && (*node)->next; node = &(*node)->next->next) {
        node_t *tmp = *node;
        *node = (*node)->next;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
}

int main() {
    ...
    swap_pair(&head);
    ...
}
```

* **`reverse`** 
```c=
/* Before */
node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next;
        head->next = cursor;
        cursor = head;
        head = next;
    }
    return cursor;
}

int main() {
    ...
    head = reverse(head);
    ...
}
```
```c=
/* After */
void reverse(node_t **indirect)
{
    node_t *cursor = NULL;
    while (*indirect) {
        node_t *next = (*indirect)->next;
        (*indirect)->next = cursor;
        cursor = *indirect;
        *indirect = next;
    }
    *indirect = cursor;
}

int main() {
    ...
    reverse(&head);
    ...
}
```

3. Make **`reverse`** recursive:
```c=
/* Before */
void reverse(node_t **indirect)
{
    node_t *cursor = NULL;
    while (*indirect) {
        node_t *next = (*indirect)->next;
        (*indirect)->next = cursor;
        cursor = *indirect;
        *indirect = next;
    }
    *indirect = cursor;
}
```
```c=
/* After */
void reverse(node_t **indirect)
{
    *indirect = rev_recursive(*indirect, NULL);
}

node_t *rev_recursive(node_t *current, node_t *prev) {
    node_t *next = current->next;
    
    current->next = prev;
    if (!next) 
        return current;

    return rev_recursive(next, current);
}
```
4. Implement [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) into SLL, and try to minimize the memory consumption:

```c=
#include <stdlib.h>
#include <time.h>
...

void fisher_yates_shuffle(node_t **head_address) {
    int count = 0;
    node_t **indirect = head_address;

    /* Counts the number of nodes in the list */
    while (*indirect) {
        indirect = &(*indirect)->next;
        count++;
    }

    node_t **node = malloc(sizeof(node_t*) * (count + 1));
    indirect = head_address;
    count = 0;

    /* Stores the addresses of each node in the list */
    while (*indirect) {
        node[count++] = *indirect;
        indirect = &(*indirect)->next;
    }
    node[count] = NULL;

    /* Shuffles the addresses of each node */
    for (int i = count - 1; i >= 1; i--) {
        int target = rand() % (i + 1);
        node_t *tmp = node[i];
        node[i] = node[target];
        node[target] = tmp;
    }

    /* Reconnects each node */
    for (int i = 0; i < count; i++)
        node[i]->next = node[i + 1];
    
    /* Updates head */
    *head_address = node[0];

    free(node);
}

int main() {
    srand(time(NULL));
    ...
    fisher_yates_shuffle(&head);
    ...
}

```
