# 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);
...
}
```
Sign in with Wallet
Connect another wallet