---
title: '2020q3 Homework1 (quiz1)'
tags: linux2020
---
# 2020q3 Homework1 (quiz1)
contributed by < `ChongMingWei` >
## Outline
[TOC]
## 環境
```shell
$ uname -a
Linux cmw-System-Product-Name 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
## 作業要求
* 重新回答[第 1 周測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)，連同附帶的「延伸問題」。
* 解釋程式運作原理時，應提供對應的 [Graphviz](https://graphviz.org/) 圖例，可參照 [Linked List 題目 1 + 分析](https://hackmd.io/@sysprog/linked-list-quiz)
* 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb) 和 [Linked list 題目分析](https://hackmd.io/s/HyELy5bTz) 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及==進行相關實驗==。
## 解題流程
### 測驗 1
#### Linked list structure
```cpp
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
__node initialization:
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record];
a [label="{ <val> value | <next> next }"]
b [label="{ <val> NULL}"];
a:next -> b:val [arrowtail=dot, dir=both];
}
```
:::danger
詳閱 Graphviz 文件，避免上圖 "next" 文字標籤和箭頭重疊。良好的文件撰寫也是軟體工程師必備素質之一。
:notes: jserv
:::
linked list:
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record];
a [label="{ <val> value | <next> next }"]
b [label="{ <val> value | <next> next }"]
c [label="{ <val> NULL}"];
a:next -> b:val [arrowtail=dot, dir=both];
b:next -> c:val [arrowtail=dot, dir=both];
}
```
#### void add_entry(node_t **head, int new_value);
:::info
In function *void addentry*, we take a pointer to pointer (which points to the pointer to head node) and value as input.
After we initialize the new node, we use a while loop to find the tail node.
Finally, link the list and the new node
:::
```c=
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;
assert(new_node);//AA1
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node;//AA2
}
```
Assign head (which is the pointer to pointer to head node) to indirect.
```cpp
#3 node_t **indirect = head;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
indirect [label="indirect"];
head [label="pointer to head node"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> new_value | <next> next }"];
b [label="{ <val> NULL}"];
a:next -> b:val [arrowtail=dot, dir=both, arrowsize=1];
color=blue;
}
{ rank = same; indirect;head;};
head->a;
indirect->head;
}
```
Create a new node.
```cpp
#5 node_t *new_node = malloc(sizeof(node_t));
#6 new_node->value = new_value;
#7 new_node->next = NULL;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record];
a [label="{ <val> new_value | <next> next }"]
b [label="{ <val> NULL}"];
a:next -> b:val [arrowtail=dot, dir=both];
}
```
To check if new_node is sucessfully created.
```cpp
#9 assert(new_node);//AA1
```
To find the tail of linked list.
```cpp
#10 while (*indirect)
#11 indirect = &(*indirect)->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
indirect [label="indirect\n(moves in each iteration)"];
head [label="pointer to head node"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> new_value | <next> next }"];
b [label="{ <val> ... }"];
c [label="{ <val> NULL}"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c [arrowtail=dot, dir=both];
color=blue;
}
{ rank = same; indirect;head;};
head->a;
indirect->head;
}
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
indirect [label="indirect\n(stops when it points to the pointer to NULL)"];
head [label="pointer to NULL"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> new_value | <next> next }"];
b [label="{ <val> ... }"];
c [label="{ <val> NULL}"];
a:next:a -> b:val [arrowtail=dot, dir=both];
b:c:b -> c [arrowtail=dot, dir=both];
color=blue;
}
{ rank = same; indirect;head;};
head->c;
indirect->head;
}
```
Assign the pointer (which points to new_node) to *indirect. So we insert a new node at the end of the
```cpp
#12 *indirect = new_node;//AA2
```
Other ideas-Modify line 10-12
```c=
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;
assert(new_node);//AA1
while ((*indirect)->next)
indirect = &(*indirect)->next;
(*indirect)->next = new_node;//AA2
}
```
**Problem**:
1. When firstly add node, **indirect* will point to *NULL*. The while loop will fail.
**Solution:** Use *if* to check if it is first time node adding.
```c=
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;
assert(new_node);
if(!*indirect){
*indirect = new_node;
return;
}
while ((*indirect)->next){
indirect = &(*indirect)->next;
}
(*indirect)->next = new_node;
}
```
#### node_t *find_entry(node_t *head, int value)
:::info
In function *node_t \*find_entry*, we take a pointer which points to head node and value as input.
Use a for loop to find the address of target
:::
```c=
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next)
/* interate */;
return current;
}
```
Assign the adrress of head node to *current*.
```cpp
#3 node_t *current = head;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
head [label="head"];
current [label="current"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> new_value | <next> next }"];
b [label="{ <val> ... }"];
c [label="{ <val> NULL}"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c [arrowtail=dot, dir=both];
color=blue;
}
head->a;
current->a;
}
```
In the for loop, check if the value of current node matches the target value. Then leave the for loop and return the address of the node.
```cpp
#4 for (; current && current->value != value; current = current->next)
#5 /* interate */;
#6 return current;
```
Start
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
head [label="head"];
current [label="current"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> new_value | <next> next }"];
b [label="{ <val> ... }"];
c [label="{ <val> value | <next> next }"];
d [label="{ <val> ... }"];
e [label="{ <val> NULL}"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
}
head->a;
current->a;
}
```
Move the pointer *current*. If find the target value, return the address.
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
head [label="head"];
current [label="current\n(current is exsisting and \nvalue matched)"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> new_value | <next> next }"];
b [label="{ <val> ... }"];
c [label="{ <val> value | <next> next }"];
d [label="{ <val> ... }"];
e [label="{ <val> NULL}"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
}
{rank=same; head; current}
head->a;
current->c:value;
}
```
#### void remove_entry
:::info
In function *void remove_entry*, we take a pointer to pointer (which points to the pointer to head node) and pointer to removed target as input.
Use a for loop to find the address of target.
If the target is found, skip it and link previous one to next one.
:::
```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);
}
```
Assign head (which is the pointer to pointer to head node) to indirect.
```cpp
#3 node_t **indirect = head;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
indirect [label="indirect\n(moved in each iteration)"];
head [label="pointer to head node"];
entry [label="entry"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> new_value | <next> next }"];
b [label="{ <val> ... }"];
c [label="{ <val> NULL}"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c [arrowtail=dot, dir=both];
color=blue;
}
{ rank = same; indirect;head;};
head->a;
indirect->head;
}
```
To find the node matched *entry*, then skip it and free the memory.
```cpp
#5 while ((*indirect) != entry)
#6 indirect = &(*indirect)->next;
#7
#8 *indirect = entry->next;
#9 free(entry);
```
Start
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
indirect [label="indirect\n(moved in each iteration)"];
head [label="pointer to head node"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> new_value | <next> next }"];
b [label="{ <val> ... }"];
c [label="{ <val> value | <next> next }"];
d [label="{ <val> ... }"];
e [label="{ <val> NULL}"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
}
{rank=same; head; indirect}
entry->c:value
indirect->head;
head->a;
}
```
When *indirect* matches *entry*, leave while loop.
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
indirect [label="*indirect"];
head [label="pointer to head node"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> new_value | <next> next }"];
b [label="{ <val> ... }"];
c [label="{ <val> value | <next> next }"];
d [label="{ <val> ... }"];
e [label="{ <val> NULL}"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
}
{rank=same; head; indirect}
entry->c:value
indirect->c:value;
head->a;
}
```
Skip the *entry* node. Link previous and next ones.
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
indirect [label="*indirect"];
head [label="pointer to head node"];
node [shape=record];
subgraph cluster_linked_list{
label = "linked_list";
a [label="{ <val> new_value | <next> next }"];
b [label="{ <val> ... }"];
c [label="{ <val> value | <next> next }"];
d [label="{ <val> ... }"];
e [label="{ <val> NULL}"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both, style=dashed];
c:next -> d:val [arrowtail=dot, dir=both, style=dashed];
b -> d:val [arrowtail=dot, dir=both];
color=blue;
d -> e:val [arrowtail=dot, dir=both];
color=blue;
}
{rank=same; head; indirect}
entry->c:value
indirect->c:value;
head->a;
}
```
Free the memory.
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
indirect [label="*indirect"];
head [label="pointer to head node"];
node [shape=record];
c [label="{ <val> value | <next> next }" style=filled];
subgraph cluster_linked_list{
label = "linked_list";
a [label="{ <val> new_value | <next> next }"];
b [label="{ <val> ... }"];
d [label="{ <val> ... }"];
e [label="{ <val> NULL}"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> d:val [arrowtail=dot, dir=both];
color=blue;
d -> e:val [arrowtail=dot, dir=both];
color=blue;
}
{rank=same; head; indirect}
entry->c:value
indirect->c:value;
head->a;
}
```
#### node_t *swap_pair(node_t *head)
:::info
In function *node_t \*swap_pair*, we take a pointer (which points to head node) as input.
Use a for loop to swap each pair of nodes.
:::
```c=
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) { //BB1
node_t *tmp = *node;
*node = (*node)->next;//BB2
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
Assign address of pointer to *head* node to *node* initially.
If reach the end of the linked list, leave the for loop.
For each for loop, assign the address of the pointer pointing to next 2 nodes to *node*.
```cpp
#3 for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) { //BB1
```
**For loop starts**
```cpp
#4 node_t *tmp = *node;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; node_t;tmp}
node_t->head;
tmp->a;
head->a;
}
```
```cpp
#5 *node = (*node)->next;//BB2
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; node_t;tmp}
node_t->head;
tmp->a;
head->b:head;
}
```
```cpp
#6 tmp->next = (*node)->next;//BB2
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next:s -> c:value [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; node_t;tmp}
node_t->head;
tmp->a;
head->b:value;
}
```
```cpp
#7 (*node)->next = tmp;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next:e -> c:value [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; node_t;tmp}
node_t->head;
tmp->a;
head->b:value;
}
```
Move to next for loop:
*node is the address of node with value 3 and (*node)->next is the address of the node with value4.
So, continue.
```cpp
#3 for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) { //BB1
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next:e -> c:value [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; node_t}
node_t->a:next;
head->b:value;
}
```
```cpp
#4 node_t *tmp = *node;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next:e -> c:value [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; node_t;tmp}
node_t->a:next;
tmp->c;
head->b:value;
}
```
```cpp
#5 *node = (*node)->next;//BB2
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next:e -> d:value [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; node_t;tmp}
node_t->a:next;
tmp->c;
head->b:value;
}
```
```cpp
#6 tmp->next = (*node)->next;//BB2
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next:e -> d:value [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> e:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; node_t;tmp}
node_t->a:next;
tmp->c;
head->b:value;
}
```
```cpp
#7 (*node)->next = tmp;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next:e -> d:value [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> e:val [arrowtail=dot, dir=both];
d:next -> c:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; node_t;tmp}
node_t->a:next;
tmp->c;
head->b:value;
}
```
Move to next for loop:
*node is the address of node with value 5 and (*node)->next is NULL.
So, leave for loop.
```cpp
#3 for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) { //BB1
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next:e -> d:value [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> e:val [arrowtail=dot, dir=both];
d:next -> c:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; node_t;tmp}
node_t->c:next;
tmp->c;
head->b:value;
}
```
```cpp
#9 return head;
```
#### void swap_pair_modified
:::info
In function *swap_pair_modified*, we take a pointer to pointer (which points to the pointer to head node) as input.
Use same algorithm as in *node_t \*swap_pair_modified*.
:::
```c=
void swap_pair_modified(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;
}
}
```
Assign address of pointer to *head* node to *node* initially.
If reach the end of the linked list, leave the for loop.
For each for loop, assign the address of the pointer pointing to next 2 nodes to *node*.
```cpp
#3 for (node_t **node = head; *node && (*node)->next; node = &(*node)->next->next) { //BB1
```
**For loop starts**
```cpp
#4 node_t *tmp = *node;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="pointer to head node"];
head_pt [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; head_pt; node_t; tmp}
head_pt->head;
node_t->head;
tmp->a;
head->a;
}
```
```cpp
#5 *node = (*node)->next;//BB2
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="pointer to head node"];
head_pt [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; head_pt; node_t; tmp}
head_pt->head;
node_t->head;
tmp->a;
head->b:value;
}
```
```cpp
#6 tmp->next = (*node)->next;//BB2
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="pointer to head node"];
head_pt [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next -> c:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; head_pt; node_t; tmp}
head_pt->head;
node_t->head;
tmp->a;
head->b:value;
}
```
```cpp
#7 (*node)->next = tmp;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="pointer to head node"];
head_pt [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next -> c:val [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; head_pt; node_t; tmp}
head_pt->head;
node_t->head;
tmp->a;
head->b:value;
}
```
Move to next for loop: *\*node* is the address of node with value3 and (*node)->next is address of node with value4.
So, continues.
```cpp
#3 for (node_t **node = head; *node && (*node)->next; node = &(*node)->next->next) { //BB1
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
head [label="pointer to head node"];
head_pt [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; head_pt; node_t}
head_pt->head;
node_t->b:next;
head->a;
}
```
**For loop starts**
```cpp
#4 node_t *tmp = *node;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="pointer to head node"];
head_pt [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; head_pt; node_t; tmp}
head_pt->head;
node_t->b:next;
tmp->c:value;
head->a;
}
```
```cpp
#5 *node = (*node)->next;//BB2
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="pointer to head node"];
head_pt [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b:next -> d:val [arrowtail=dot, dir=both];
c:next -> d:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; head_pt; node_t; tmp}
head_pt->head;
node_t->b:next;
tmp->c:value;
head->a;
}
```
```cpp
#6 tmp->next = (*node)->next;//BB2
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="pointer to head node"];
head_pt [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b:next -> d:val [arrowtail=dot, dir=both];
c:next -> e:val [arrowtail=dot, dir=both];
d -> e:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; head_pt; node_t; tmp}
head_pt->head;
node_t->b:next;
tmp->c:value;
head->a;
}
```
```cpp
#7 (*node)->next = tmp;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
tmp [label="tmp"];
head [label="pointer to head node"];
head_pt [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b:next -> d:val [arrowtail=dot, dir=both];
c:next -> e:val [arrowtail=dot, dir=both];
d:next -> c:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; head_pt; node_t; tmp}
head_pt->head;
node_t->b:next;
tmp->c:value;
head->a;
}
```
Move to next for loop: *\*node* is the address of node with value 5 and (*node)->next is NULL. So, leave for loop.
```cpp
#3 for (node_t **node = head; *node && (*node)->next; node = &(*node)->next->next) { //BB1
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_t [label="node"];
head [label="pointer to head node"];
head_pt [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
e [label="{ <val> value5 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b:next -> d:val [arrowtail=dot, dir=both];
c:next -> e:val [arrowtail=dot, dir=both];
d:next -> c:val [arrowtail=dot, dir=both];
color=blue;
e:next:e ->null:w;
}
{rank=same; head; head_pt; node_t}
head_pt->head;
node_t->c:next;
head->a;
}
```
#### node_t *reverse
:::info
In function *node_t \*reverse*, we take a pointer (which points to head node) as input.
Use a while loop to reverse the linked list.
:::
```c=
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;
}
```
Pointer cursor is used for pointing to current reversed linked list.
```cpp
#3 node_t *cursor = NULL;
```
The concept is: **Create another linked list which has the head node cursor.**
In the while loop, we check if head is NULL and move one node from original linked list to new linked list (with cursor as head node) each time.
```cpp
#4 while (head) {
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor}
cursor->null
head->a;
}
```
```cpp
#5 node_t *next = head->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor}
next->b:value;
cursor->null
head->a;
}
```
```cpp
#6 head->next = cursor;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor}
cursor->null;
next->b:value;
head->a;
}
```
```cpp
#7 cursor = head;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor}
cursor->a:value;
next->b:value;
head->a;
}
```
```cpp
#8 head = next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor}
cursor->a:value;
next->b:value;
head->b:value;
}
```
head is the address of the node with value2.
So continues.
```cpp
#4 while (head) {
```
```cpp
#5 node_t *next = head->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor}
cursor->a:value;
next->c:value;
head->b:value;
}
```
```cpp
#6 head->next = cursor;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor}
cursor->a:value;
next->c:value;
head->b:value;
}
```
```cpp
#7 cursor = head;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor}
cursor->b:value;
next->c:value;
head->b:value;
}
```
```cpp
#8 head = next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor}
cursor->b:value;
next->c:value;
head->c:value;
}
```
head is the address of the node with value3.
So continues.
```cpp
#4 while (head) {
```
```cpp
#5 node_t *next = head->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor}
cursor->b:value;
next->null;
head->c:value;
}
```
```cpp
#6 head->next = cursor;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> b:val [arrowtail=dot, dir=both];
}
{rank=same; head; cursor}
cursor->b:value;
next->null;
head->c:value;
}
```
```cpp
#7 cursor = head;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> b:val [arrowtail=dot, dir=both];
}
{rank=same; head; cursor}
cursor->c:value;
next->null;
head->c:value;
}
```
```cpp
#8 head = next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> b:val [arrowtail=dot, dir=both];
}
{rank=same; head; cursor}
cursor->c:value;
next->null;
head->null;
}
```
head is NULL.
So leave the while loop.
```cpp
#4 while (head) {
```
#### void reverse_modified
:::info
In function *reverse_modified*, we take a pointer to pointer (which points to the pointer to head node) as input.
Use same algorithm as in *void reverse*.
:::
```c=
void reverse_modified(node_t **head)
{
node_t **indirect = head;
node_t *cursor = NULL;
while (*indirect) {
node_t *next = (*indirect)->next;
(*indirect)->next = cursor;
cursor = (*indirect);
(*indirect) = next;
}
*head = cursor;
}
```
```cpp
#3 node_t **indirect = head;
#4 node_t *cursor = NULL;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->null
head_pt->a:value;
indirect->head_pt;
head->head_pt;
}
```
*\*indirect* is the pointer to head node, not NULL.
So enter in while loop.
```cpp
#5 while (*indirect) {
```
```cpp
#6 node_t *next = (*indirect)->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->null
head_pt->a:value;
indirect->head_pt;
head->head_pt;
next->b:value;
}
```
```cpp
#7 (*indirect)->next = cursor;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->null
head_pt->a:value;
indirect->head_pt;
head->head_pt;
next->b:value;
}
```
```cpp
#8 cursor = (*indirect);
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->a:value;
head_pt->a:value;
indirect->head_pt;
head->head_pt;
next->b:value;
}
```
```cpp
#9 (*indirect) = next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->a:value;
head_pt->b:value;
indirect->head_pt;
head->head_pt;
next->b:value;
}
```
*\*indirect* is the pointer to node with value2, not NULL.
So continues.
```cpp
#5 while (*indirect) {
```
```cpp
#6 node_t *next = (*indirect)->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->a:value;
head_pt->b:value;
indirect->head_pt;
head->head_pt;
next->c:value;
}
```
```cpp
#7 (*indirect)->next = cursor;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->a:value;
head_pt->b:value;
indirect->head_pt;
head->head_pt;
next->c:value;
}
```
```cpp
#8 cursor = (*indirect);
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->b:value;
head_pt->b:value;
indirect->head_pt;
head->head_pt;
next->c:value;
}
```
```cpp
#9 (*indirect) = next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->b:value;
head_pt->c:value;
indirect->head_pt;
head->head_pt;
next->c:value;
}
```
*\*indirect* is the pointer to node with value3, not NULL.
So continues.
```cpp
#5 while (*indirect) {
```
```cpp
#6 node_t *next = (*indirect)->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->b:value;
head_pt->c:value;
indirect->head_pt;
head->head_pt;
next->null;
}
```
```cpp
#7 (*indirect)->next = cursor;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> b:value [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->b:value;
head_pt->c:value;
indirect->head_pt;
head->head_pt;
next->null;
}
```
```cpp
#8 cursor = (*indirect);
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> b:value [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->c:value;
head_pt->c:value;
indirect->head_pt;
head->head_pt;
next->null;
}
```
```cpp
#9 (*indirect) = next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
next [label="next"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> b:value [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->c:value;
head_pt->null;
indirect->head_pt;
head->head_pt;
next->null;
}
```
*\*indirect* is NULL.
So leave while loop.
```cpp
#5 while (*indirect) {
```
Assign *cursor* to *\*head*.
```cpp
#11 *head = cursor;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
cursor [label="cursor"];
head [label="head"];
indirect [label="indirect"]
head_pt [label="pointer to head node"]
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:val [arrowtail=dot, dir=both];
c:next -> b:value [arrowtail=dot, dir=both];
}
{rank=same; head; cursor; indirect;}
cursor->c:value;
head_pt->c:value;
indirect->head_pt;
head->head_pt;
}
```
#### node_t \*rev_recursive
Use algorithm from [Recursive Reverse Linked List](https://www.geeksforgeeks.org/reverse-a-linked-list/)
```
1) Divide the list in two parts - first node and
rest of the linked list.
2) Call reverse for the rest of the linked list.
3) Link rest to first.
4) Fix head pointer
```
```c=
node_t *rev_recursive(node_t *head)
{
if (!head || !head->next) {
return head;
}
node_t *first = head;
node_t *rest = head->next;
rest = rev_recursive(rest);
first->next->next = first;
first->next = NULL;
return rest;
}
```
To check if linked list is NULL and if it reaches the tail.
```cpp
#3 if (!head || !head->next) {
#4 return head;
#5 }
```
```cpp
#6 node_t *first = head;
#7 node_t *rest = head->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
first [label="first"];
rest [label="rest"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
first -> a:value;
rest -> b:value;
head-> a;
}
```
Recursive call and assign the return pointer to temporary head node to *rest*.
```cpp
#8 rest = rev_recursive(rest);
```
Assign first to the *next* pointer of the next node and NULL to *next* pointer of current node.
Take final round as example.
```cpp
#9 first->next->next = first;
#10 first->next = NULL;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
first [label="first"];
rest [label="rest"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> b:value [arrowtail=dot, dir=both];
b:next -> null [arrowtail=dot, dir=both];
c:next -> b:value [arrowtail=dot, dir=both];
}
first -> a:value;
rest -> c:value;
head-> a;
}
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
first [label="first"];
rest [label="rest"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> null [arrowtail=dot, dir=both];
b:next -> a:value [arrowtail=dot, dir=both];
c:next -> b:value [arrowtail=dot, dir=both];
}
first -> a:value;
rest -> c:value;
head-> a;
}
```
Return the pointer to head node in each recursion.
```cpp
#11 return rest;
```
#### void print_list
:::info
In function *print_list*, we take a pointer (which points to head node) as input.
Use a for loop to traverse all nodes and print their values.
:::
```c=
void print_list(node_t *head)
{
for (node_t *current = head; current; current = current->next)
printf("%d ", current->value);
printf("\n");
}
```
Assign the address of head node to *current*, then check if current is NULL.
For each loop, update current with the address of next node.
```cpp
#3 for (node_t *current = head; current; current = current->next)
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
current1 [label="current (loop 1)"];
current2 [label="current (loop 2)"];
current3 [label="current (loop 3)"];
current4 [label="current (leave loop)"];
head [label="head"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
null [label="NULL"];
a:next -> b:val [arrowtail=dot, dir=both];
b -> c:val [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
}
current1->a:value;
current2->b:value;
current3->c:value;
current4->null;
head->a;
}
```
#### void Fisher_Yates_shuffle
Use the [Fisher_Yates_shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) algorithm from wikipedia.
```cpp
//Pseudo code
//To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
```
To exchange a[j] and a[i] in linked list:
1. Save the pointer to the previous node of a[j] and a[i].
2. Take pointer of **the previous node of a[j]** and keep the pointers of **next and next 2 nodes**.
3. Exchange the previous and next links of a[j] and a[i].
Example:
Suppose i = 3 and j = 1:
- Step1
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_prei [label="node_prei"];
node_prej [label="node_prej"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> b:value [arrowtail=dot, dir=both];
b:next -> c:value [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
node_prei->c:value;
node_prej->a:value;
}
```
- Step2
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_prei [label="node_prei"];
node_prej [label="node_prej"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> b:value [arrowtail=dot, dir=both];
b:next -> c:value [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
node_prei->c:value;
node_prej->a:value;
tmp_prej->b:value;
tmp_nextj->c:value;
}
```
- Step 3
```cpp
node_prej->next->next = node_prei->next->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_prei [label="node_prei"];
node_prej [label="node_prej"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> b:value [arrowtail=dot, dir=both];
b:next -> null [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
node_prei->c:value;
node_prej->a:value;
tmp_prej->b:value;
tmp_nextj->c:value;
}
```
```cpp
node_prej->next = node_prei->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_prei [label="node_prei"];
node_prej [label="node_prej"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> d:value [arrowtail=dot, dir=both];
b:next -> null [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
node_prei->c:value;
node_prej->a:value;
tmp_prej->b:value;
tmp_nextj->c:value;
}
```
```cpp
node_prei->next->next = tmp_next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_prei [label="node_prei"];
node_prej [label="node_prej"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> d:value [arrowtail=dot, dir=both];
b:next -> null [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> c:value [arrowtail=dot, dir=both];
}
node_prei->c:value;
node_prej->a:value;
tmp_prej->b:value;
tmp_nextj->c:value;
}
```
```cpp
node_prei->next = tmp_pre;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_prei [label="node_prei"];
node_prej [label="node_prej"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> d:value [arrowtail=dot, dir=both];
b:next -> null [arrowtail=dot, dir=both];
c:next -> b:value [arrowtail=dot, dir=both];
d:next -> c:value [arrowtail=dot, dir=both];
}
node_prei->c:value;
node_prej->a:value;
tmp_prej->b:value;
tmp_nextj->c:value;
}
```
3 additional conditions need to be considered:
1. j equals to i
2. j equals to 0
3. j is next to i
- For condition 1:
Just skip that round.
- For condition 2:
We set head node as node_prej.
```cpp
node_prej = *indirect;
tmp_pre = *head;
tmp_next = (*head)->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_prej [label="node_prej"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> b:value [arrowtail=dot, dir=both];
b:next -> c:value [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
node_prej->a:value;
tmp_prej->a:value;
tmp_nextj->b:value;
}
```
- Case 1: node_prej and node_prei are pointing to same node
Which means i = 1.
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
head [label="*head"];
node_prej [label="node_prej"];
node_prei [label="node_prei"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> b:value [arrowtail=dot, dir=both];
b:next -> c:value [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
head->a:value;
node_prei->a:value;
node_prej->a:value;
tmp_prej->a:value;
tmp_nextj->b:value;
}
```
```cpp
(*head)->next = node_prei->next->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
head [label="*head"];
node_prej [label="node_prej"];
node_prei [label="node_prei"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> c:value [arrowtail=dot, dir=both];
b:next -> c:value [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
head->a:value;
node_prei->a:value;
node_prej->a:value;
tmp_prej->a:value;
tmp_nextj->b:value;
}
```
```cpp
*head = tmp_next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
head [label="*head"];
node_prej [label="node_prej"];
node_prei [label="node_prei"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> c:value [arrowtail=dot, dir=both];
b:next -> c:value [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
head->b:value;
node_prei->a:value;
node_prej->a:value;
tmp_prej->a:value;
tmp_nextj->b:value;
}
```
```cpp
(*head)->next = tmp_pre;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
head [label="*head"];
node_prej [label="node_prej"];
node_prei [label="node_prei"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> c:value [arrowtail=dot, dir=both];
b:next -> a:value [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
head->b:value;
node_prei->a:value;
node_prej->a:value;
tmp_prej->a:value;
tmp_nextj->b:value;
}
```
- Case 2: node_prej and node_prei are pointing to different nodes.
(Suppose i = 2 here)
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
head [label="*head"];
node_prej [label="node_prej"];
node_prei [label="node_prei"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> b:value [arrowtail=dot, dir=both];
b:next -> c:value [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
head->a:value;
node_prei->b:value;
node_prej->a:value;
tmp_prej->a:value;
tmp_nextj->b:value;
}
```
```cpp
(*head)->next = node_prei->next->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
head [label="*head"];
node_prej [label="node_prej"];
node_prei [label="node_prei"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> d:value [arrowtail=dot, dir=both];
b:next -> c:value [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
head->a:value;
node_prei->b:value;
node_prej->a:value;
tmp_prej->a:value;
tmp_nextj->b:value;
}
```
```cpp
*head = node_prei->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
head [label="*head"];
node_prej [label="node_prej"];
node_prei [label="node_prei"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> d:value [arrowtail=dot, dir=both];
b:next -> c:value [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
head->c:value;
node_prei->b:value;
node_prej->a:value;
tmp_prej->a:value;
tmp_nextj->b:value;
}
```
```cpp
node_prei->next->next = tmp_next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
head [label="*head"];
node_prej [label="node_prej"];
node_prei [label="node_prei"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> d:value [arrowtail=dot, dir=both];
b:next -> c:value [arrowtail=dot, dir=both];
c:next -> b:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
head->c:value;
node_prei->b:value;
node_prej->a:value;
tmp_prej->a:value;
tmp_nextj->b:value;
}
```
```cpp
node_prei->next = tmp_pre;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
head [label="*head"];
node_prej [label="node_prej"];
node_prei [label="node_prei"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> d:value [arrowtail=dot, dir=both];
b:next -> a:value [arrowtail=dot, dir=both];
c:next -> b:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
head->c:value;
node_prei->b:value;
node_prej->a:value;
tmp_prej->a:value;
tmp_nextj->b:value;
}
```
- For condition 3:
We use different exchange method.
Suppose i = 3 and j = 2:
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_prei [label="node_prei"];
node_prej [label="node_prej"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> b:value [arrowtail=dot, dir=both];
b:next -> c:value [arrowtail=dot, dir=both];
c:next -> d:value [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
node_prei->c:value;
node_prej->b:value;
tmp_prej->c:value;
tmp_nextj->d:value;
}
```
```cpp
node_prei->next = tmp_next->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_prei [label="node_prei"];
node_prej [label="node_prej"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> b:value [arrowtail=dot, dir=both];
b:next -> c:value [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
node_prei->c:value;
node_prej->b:value;
tmp_prej->c:value;
tmp_nextj->d:value;
}
```
```cpp
node_prej->next = tmp_next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_prei [label="node_prei"];
node_prej [label="node_prej"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> b:value [arrowtail=dot, dir=both];
b:next -> d:value [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
d:next -> null [arrowtail=dot, dir=both];
}
node_prei->c:value;
node_prej->b:value;
tmp_prej->c:value;
tmp_nextj->d:value;
}
```
```cpp
tmp_next->next = tmp_pre;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=plaintext];
node_prei [label="node_prei"];
node_prej [label="node_prej"];
tmp_prej [label="tmp_prej"];
tmp_nextj [label="tmp_nextj"];
subgraph cluster_linked_list{
label = "linked_list";
node [shape=record];
a [label="{ <val> value1 | <next> next }"];
b [label="{ <val> value2 | <next> next }"];
c [label="{ <val> value3 | <next> next }"];
d [label="{ <val> value4 | <next> next }"];
null [label="NULL"];
a:next -> b:value [arrowtail=dot, dir=both];
b:next -> d:value [arrowtail=dot, dir=both];
c:next -> null [arrowtail=dot, dir=both];
d:next -> c:value [arrowtail=dot, dir=both];
}
node_prei->c:value;
node_prej->b:value;
tmp_prej->c:value;
tmp_nextj->d:value;
}
```
Sign in with Wallet
Connect another wallet