---
tags: linux2022
---
# 2022q1 Homework (quiz1)
contributed by <`ibat10clw`>
> [quiz1](https://hackmd.io/@sysprog/linux2022-quiz1)
## Q1. 以 hash 實作 LeetCode1. Two Sum
首先從解題的函式 twoSum 開始看起
```c
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
map_t *map = map_init(10);
*returnSize = 0;
int *ret = malloc(sizeof(int) * 2);
if (!ret)
goto bail;
for (int i = 0; i < numsSize; i++) {
int *p = map_get(map, target - nums[i]);
if (p) { /* found */
ret[0] = i, ret[1] = *p;
*returnSize = 2;
break;
}
p = malloc(sizeof(int));
*p = i;
map_add(map, nums[i], p);
}
bail:
map_deinit(map);
return ret;
}
```
執行流程可以表示如下:
1. 初始化 hash_map
2. 看過所有 nums 中的元素並且同時查詢 map 中是否有 key 與 ```nums[i]``` 相加會等於 target
* 若有查到對應的元素則將 ```i``` 與 ```HT[nums[i]]``` 作為答案
* 沒有查到的話則將 ```target - nums[i]``` 作為 key, ```i``` 作為 value 並且加入 map 中
3. 將 map 釋放掉後回傳答案
接下來看 hash 的實作
```c
struct hlist_node {
struct hlist_node *next, **pprev;
};
struct hlist_head {
struct hlist_node *first;
};
```
* 先從 hlist 看起, 相關的結構共有兩個, 分別是 head 以及 node, 為了解決碰撞(collision)問題, 同樣一個 bucket 的資料會由 hlist_head 指出去的 list 串連起來
* 此外為了讓程式碼更精簡, 在 hlist_node 採用了 pointer to pointer 的方式, 這樣能夠在 delete 的操作上消除特例情況的判斷, 不需判斷要刪除的地方是否為 head 或 NULL 的情形, 但 ```**pprev``` 的指標 hlist_head 並不需要, 若與 hlist_node 共用一個 struct 則會浪費記憶體, 因此將其分開宣告
再來是 map 的本體以及 hash 的資料定義
```c
typedef struct {
int bits; struct hlist_head *ht;
} map_t;
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
* map_t 裡面的 bits 會用來決定 bucket 的數量以及用於後續的 hash function, 根據 bits 的大小會產生對應的 hlist_head , 在後續的函式解說中會更詳細說明
* hash_key 為實際資料存放的地方, 裡面有個 hlist_node 可以讓 hash_key 透過 list 的方式與 bucket 連接
### map_init
```c
map_t *map_init(int bits) {
map_t *map = malloc(sizeof(map_t));
if (!map)
return NULL;
map->bits = bits;
map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
if (map->ht) {
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
(map->ht)[i].first = NULL;
} else {
free(map);
map = NULL;
}
return map;
}
```
一開始先將傳入的參數 bits 指定給 map 的 member, 接著透過一個 macro 的實作來決定 ht 大小
```c
#define MAP_HASH_SIZE(bits) (1 << bits)
```
以 1 為底的 shift operator 可以視為 2^0^ * 2^bits^ = 2^bits^ 的操作
接下來將所有的 hlist_head 的 first 指向 NULL, 以代表目前 hash table 的各個 bucket 都是空的
### map_get
```c
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
找尋傳入的 key 是否存在 map 裡面, 如果有就回把 ```hash_key->data``` 的 address 傳回去, 否則回傳空指標
### find_key
```c
static struct hash_key *find_key(map_t *map, int key) {
struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
for (struct hlist_node *p = head->first; p; p = p->next) {
struct hash_key *kn = container_of(p, struct hash_key, node);
if (kn->key == key)
return kn;
}
return NULL;
}
```
首先透過 hash function 找出 key 可能位於哪個 bucket
之後從該個 bucket 的 head 出發尋訪整個 list 如果有找到某個 hash_key 的 key 與傳入參數的 key 相等, 則回傳該個 hash_key, 否則回傳 NULL
例如 hash 出來的值為2, 那則順著這個 list 沿路比對 key, 若比對成功的話就將這個 hash_key 的 address 回傳(附圖上先忽略了 pprev 的link)
### hash
```c
#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits) {
/* High bits are more random, so use them. */
return (val * GOLDEN_RATIO_32) >> (32 - bits);
}
```
一個好的 hash function 須滿足三個條件
1. 容易計算
2. 每個 bucket 被分配到的機率盡量相等
3. 減少碰撞發生
可以看到這個 hash function 為單純的四則運算在加上 shift, 有滿足容易計算的性質
第二和第三個性質待驗證
這個函數的功能也相當容易理解, 就是根據傳入的 val 和 bits 回傳該將資料放在哪一個 bucket
實作部份會將 val 乘上 GOLDEN_RATIO_32 後再把 (32 - bits) 的量透過 right shift 去掉, 以本題實作來說 bits 為 10, 32 bits 的資料再去掉 22 bits 後恰好剩下 10 bits, 因此也能保證他的值會位於 0 ~ 1023 之間
### map_add
```c=
void map_add(map_t *map, int key, void *data)
{
struct hash_key *kn = find_key(map, key);
if (kn)
return;
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
AAA;
if (first)
first->pprev = &n->next;
h->first = n;
BBB;
}
```
首先查詢輸入的 key 是否已存在 map 中, 若有找到根據 ```find_key``` 的寫法,確認 ``` kn != NULL```, 若已存在 map 中則直接離開函式
由於沒有找到所以 ```kn``` 會是空指標, 為他分配一個 ```hash_key``` 大小的記憶體空間, 同時將資料初始化
然後透過 hash function 找出應該把他放在哪一個 bucket , 將這個 bucket 的資訊存在變數 h, hash_key 的 node 存在變數 n, 該 bucket 的第一個元素存在變數 first
這時先來觀察 13~15 行中給出的資訊, 若 first 不為 NULL 則表示這個 bucket 至少存在一個資料, 我們將 kn 加入在 list 的 head 端, 因此先更新了原先 first 的 pprev, 最後在將 first 更新成 n
最後來推斷 AAA 與 BBB 分別的情形
如上圖所示, 每個 node 都有 pprev 與 next 需要處理, 顯然我們還沒對新加入的資料 kn 的 node 做處理
又因為是插入在 head 那一端因此需要將 next 指向原先的第一個 node, pprev 指向 hlist_head.first
* AAA
* 在 15 行後我們就失去了原先 first 的資訊了, 所以根據題目選項這邊一定要先把 next 指過去
* ```n->next = first```
* BBB
* 由於 AAA 以更新 next, 這邊將 pprev 也指向 hlist_head.first
* ```n->pprev = &h->first```
### map_deinit
```c
void map_deinit(map_t *map)
{
if (!map)
return;
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
struct hlist_head *head = &map->ht[i];
for (struct hlist_node *p = head->first; p;) {
struct hash_key *kn = container_of(p, struct hash_key, node);
struct hlist_node *n = p;
p = p->next;
if (!n->pprev) /* unhashed */
goto bail;
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
bail:
free(kn->data);
free(kn);
}
}
free(map);
}
```
最後是釋放掉 map 的方法, 如果 map 不存在則直接 return
外層的 for 迴圈是為了檢查所有的 bucket, 內層的 for 迴圈則是走過這個 bucket 上的 list 並且透過 ```container_of``` 沿途釋放元素, 可以看到初始化時將 head->first 存在 p, 若 p 為空則直接結束, 否則移動 p 走訪 list
當所有的 node 釋放完畢後把 map 本身也釋放掉, 函式結束
### 答案
在 map_add 有詳細解釋思路
* AAA = ```n->next = first```
* BBB = ```n->pprev = &h->first```
## Q2. LeetCode 82. Remove Duplicates from Sorted List II
這題目的要求相當簡單, 若在 list 中有出現重複元素, 則將他們全部刪除
```c=
#include <stddef.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
if (COND1) {
/* Remove all duplicate numbers */
while (COND2)
head = head->next;
return deleteDuplicates(head->next);
}
head->next = deleteDuplicates(head->next);
return head;
}
```
### 題目分析
本題的題目首先要求補齊 COND1 和 COND2
以下是我的答案
* COND1 = ```head->next && head->val == head->next->val```
* COND2 = ```head->next && head->val == head->next->val```
先來分析遞迴的中止條件, 當 head 為空指標時才會結束遞迴呼叫, 搭配上 17 和 21 行的遞迴呼叫, 可以看到是遞迴在當前的下一個 node
再來探討兩次呼叫的區別
* 17 行中的呼叫並沒有將 return 的值存下來
* 20 行中將 return 的值存下來, 並且是串在 list 上
因此可以推測 20 行中所處理的是不重複的元素, 才會將 return value 串在 list 上
反之 13 行開始的 if block 是處理重複的元素, 當條件成立時不斷將指標向前推進, 最後做一個遞迴呼叫
### 遞迴解法
這是我一開始的想法
```c
head->val == head->next->val
```
只要發現目前 node 的值與下一個 node 相等, 就開始 remove all duplicate 的處理, 但一提交馬上遇到存取了 NULL pointer的問題
後來在 condition 前面先補上 ```head->next``` 並且用 && 做連接變成
```c
head->next && head->val == head->next->val
```
當 ```head->next``` 為空時, 後面的 ```head->next->val``` 就不會被執行了, 成功避免了存取空指標的問題, 同時因為是 AND 運算, 其中一個地方不成立也不會進去 if 的 block 裡面
### 非遞迴解法
以下是我實作的程式碼, remove 的方法參考了[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E5%BE%9E-Linux-%E6%A0%B8%E5%BF%83%E7%9A%84%E8%97%9D%E8%A1%93%E8%AB%87%E8%B5%B7)中介紹的方式
關於 remove 的部份有稍做修改, 由於 LeetCode 上的 struct 定義與 linux 裡面有所不同, head 是有帶 data 的, 同時由於 head 也可能被移除, 因此將傳入的參數改為 pointer to pointer
deleteDuplicates 是參考了 [lab0-c](https://hackmd.io/8xMSCctKQpWWSRGLiuPkfQ?view#q_delete_dup) 的方法
外層的 while 每個回合都儲存 current->val, 然後開始與 current->next 比對, 如果相等就開始刪除直到current->next->val 不相等時, 離開內層 while 並且根據 tag 來決定是否要在刪除 current
```c=
void remove_list_node(struct ListNode **list, struct ListNode *target)
{
struct ListNode **indirect = list;
while (*indirect != target){
indirect = &(*indirect)->next;
}
*indirect = target->next;
}
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
struct ListNode *current = head;
char tag = 0;
int pval;
struct ListNode* del_node;
while (current != NULL) {
pval = current->val;
while (current->next && current->next->val == pval) {
tag = 1;
del_node = current;
current = current->next;
remove_list_node(&head, del_node);
}
if(tag){
tag = 0;
del_node = current;
current = current->next;
remove_list_node(&head, del_node);
}
else
current = current->next;
}
return head;
}
```
## Q3. LeetCode 146. LRU Cache
以下為完整的測試程式
* MMM1 = ```list_for_each_entry_safe```
* MMM2 = ```list_for_each_entry```
* MMM3 = ```list_for_each_entry```
* MMM4 = ```list_last_entry```
```c=
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
LRUCache *lRUCacheCreate(int capacity)
{
LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
obj->count = 0;
obj->capacity = capacity;
INIT_LIST_HEAD(&obj->dhead);
for (int i = 0; i < capacity; i++)
INIT_LIST_HEAD(&obj->hheads[i]);
return obj;
}
void lRUCacheFree(LRUCache *obj)
{
LRUNode *lru, *n;
list_for_each_entry_safe (lru, n, &obj->dhead, dlink) {
list_del(&lru->dlink);
free(lru);
}
free(obj);
}
int lRUCacheGet(LRUCache *obj, int key)
{
LRUNode *lru;
int hash = key % obj->capacity;
list_for_each_entry (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
return lru->value;
}
}
return -1;
}
void lRUCachePut(LRUCache *obj, int key, int value)
{
LRUNode *lru;
int hash = key % obj->capacity;
list_for_each_entry (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
lru->value = value;
return;
}
}
if (obj->count == obj->capacity) {
lru = list_last_entry(&obj->dhead, LRUNode, dlink);
list_del(&lru->dlink);
list_del(&lru->hlink);
} else {
lru = malloc(sizeof(LRUNode));
obj->count++;
}
lru->key = key;
list_add(&lru->dlink, &obj->dhead);
list_add(&lru->hlink, &obj->hheads[hash]);
lru->value = value;
}
int main() {
LRUCache *lRUCache = lRUCacheCreate(2);
lRUCachePut(lRUCache, 1, 1); // cache is {1=1}
lRUCachePut(lRUCache, 2, 2); // cache is {1=1, 2=2}
printf("%d\n", lRUCacheGet(lRUCache, 1)); // return 1
lRUCachePut(lRUCache, 3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
printf("%d\n", lRUCacheGet(lRUCache, 2)); // returns -1 (not found)
lRUCachePut(lRUCache, 4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
printf("%d\n", lRUCacheGet(lRUCache, 1)); // return -1 (not found)
printf("%d\n", lRUCacheGet(lRUCache, 3)); // return 3
printf("%d\n", lRUCacheGet(lRUCache, 4)); // return 4
lRUCacheFree(lRUCache);
return 0;
}
```
編譯並執行下列程式可以得到以下輸出
```shell
$ ./LRU.out
1
-1
-1
3
4
```
### LRU cache 設計概念
* 替換機制: 當 cache 滿的時候, 將最久沒用到的資料移出去
* Put: 會分為下列情形
* cache 還有空位: 將 data 放入, 且更新 least recently used element
* cache 沒有空位: 透過 least recently used element 決定要將哪個 element 置換出去, 也需要更新 least recently used element
* Get: 會分為下列情形
* 有查到: 將 data 回傳, 同時更新 least recently used element
* 沒查到: 以 -1 當成 invalid data, 直接回傳當作查詢失敗, 不需更新 least recently used element
* 資料結構: 為了滿足快速查詢以及維持 least recently used element 的操作, 分別設計了一個簡單的 hash_map 來做查詢, 以及一個 doubly circular linked list, 以 list 的 last_entry 來辨別 least recently used element
* hhead 和 hlink 用來串連有同樣 hash value 的 LRUNode
* dhead 和 dlink 串連所有的 LRUNode
接下來講解程式碼的部份
### LRUCache & LRUNode 的結構定義
```c
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
```
* 在 LRUCache 中是不帶 node 的資料的, 裡面只存了 cache 的最大容量和目前容量兩個資訊, 以及數個 list_head 來作為 LRUNode 的 head
* capacity: 最大容量
* count: 當前容量
* dhead: 指向 LRUNode, 可以用 dlink 找到所有 Node 的資料
* 為 circular doubly 的結構
* hheads: 數量取決於 capacity 的大小, 指向有同樣(與 hhead 的 index 相等) hash_value 的 LRUNode, 從 hlink 找出去只能找到有同樣 hash_value 的 node
* 非 circular 的結構
* LRUNode 負責裡面有 hlink 與 dlink 維持 list 的結構, 此外 key 與 value 也是 node 負責儲存
### lRUCacheCreate
```c
LRUCache *lRUCacheCreate(int capacity)
{
LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
obj->count = 0;
obj->capacity = capacity;
INIT_LIST_HEAD(&obj->dhead);
for (int i = 0; i < capacity; i++)
INIT_LIST_HEAD(&obj->hheads[i]);
return obj;
}
```
* 首先會為 obj 分配記憶體空間, 除了 obj 自身的大小外, 還須算上有多少 hheads, 而 hheads 的數量由 capcacity 決定, 因此將他的 size 與 capacity 相乘
* 再來將所有的 list 初始化, 透過 INIT_LIST_HEAD 讓他們的 next 與 prev 都指向自己
### lRUCachePut
```c=
void lRUCachePut(LRUCache *obj, int key, int value)
{
LRUNode *lru;
int hash = key % obj->capacity;
list_for_each_entry (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
lru->value = value;
return;
}
}
if (obj->count == obj->capacity) {
lru = list_last_entry(&obj->dhead, LRUNode, dlink);
list_del(&lru->dlink);
list_del(&lru->hlink);
} else {
lru = malloc(sizeof(LRUNode));
obj->count++;
}
lru->key = key;
list_add(&lru->dlink, &obj->dhead);
list_add(&lru->hlink, &obj->hheads[hash]);
lru->value = value;
}
```
* 當想要把東西放進 cache 時, 首先計算傳入的 key 會對應的 hash value
* 第 5 到 9 行是沿著對應的 hhead 出發查看是否有相同的 key 已經存在 cache 中, 如果有的話就將它移動到 dhead 的 head 端, 代表剛被存取過, 由於已存在所以不需要新增資料, 因此只更新 value 便可以結束
* 第 12 到 19 行在確認 cache 是否以滿, 若滿了的話則找出 least recently used element 把它移除 cache, 根據我們的設計 least recently used element 必會存在 dhead 這條 list 的 tail 端, 若 cache 還有位置則直接分配空間, 然後將 count 遞增
* 第 20 到 23 行是將 LRUNode 分別串上 hlist 與 dlist, 位置分別會是對應 hlist 的最尾端和 dlist 的最前端, 同時將參數傳入的 key 與 value 指派給 lru
#### 以下為例圖, 其中省略了部份的 prev link, 兩張圖的 Node 是相同的
* hheads 會指向所有持有同樣 hash value 的 Node, 因此可以做到快速查詢
* dhead 則是指向所有的 Node, 並且透過 dhead->prev 可以快速找到 least recently used element
### lRUCacheGet
```c
int lRUCacheGet(LRUCache *obj, int key)
{
LRUNode *lru;
int hash = key % obj->capacity;
list_for_each_entry (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
return lru->value;
}
}
return -1;
}
```
* 要從 cache 內拿取資料時同樣要先計算 hash value, 再從對應的 hhead 出發, 如果有 key 配對上了則將這個 Node 移動到 dhead 的 head 端, 並回傳對應的 value, 否則回傳 -1 表示 cache miss
### lRUCacheFree
```c
void lRUCacheFree(LRUCache *obj)
{
LRUNode *lru, *n;
list_for_each_entry_safe (lru, n, &obj->dhead, dlink) {
list_del(&lru->dlink);
free(lru);
}
free(obj);
}
```
* 由於我們能透過 dlink 找到所有的資料, 因此沿著 dhead 沿路將記憶體是空間釋放出來即可, 最後再把 cache 給 free 就結束了
### 解題思路
#### MMM1
```c=
void lRUCacheFree(LRUCache *obj)
{
LRUNode *lru, *n;
MMM1 (lru, n, &obj->dhead, dlink) {
list_del(&lru->dlink);
free(lru);
}
free(obj);
}
```
* 這段程式碼位於 lRUCacheFree 裡面, 可以看到第 5, 6 在 delete , 為了確保不會丟失 list 的資訊這邊應該選擇 ```list_for_each_entry_safe```
#### MMM2
```c=
int lRUCacheGet(LRUCache *obj, int key)
{
LRUNode *lru;
int hash = key % obj->capacity;
MMM2 (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
return lru->value;
}
}
return -1;
}
```
* 當我們想確認某個元素是否存在 cache 裡面時必須走過對應 hhead 延伸出去的 list 才能確定結果是 hit or miss, 因此在這裡選擇 ```list_for_each_entry```
#### MMM3 MMM4
```c=
void lRUCachePut(LRUCache *obj, int key, int value)
{
LRUNode *lru;
int hash = key % obj->capacity;
MMM3 (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
lru->value = value;
return;
}
}
if (obj->count == obj->capacity) {
lru = MMM4(&obj->dhead, LRUNode, dlink);
list_del(&lru->dlink);
list_del(&lru->hlink);
} else {
lru = malloc(sizeof(LRUNode));
obj->count++;
}
lru->key = key;
list_add(&lru->dlink, &obj->dhead);
list_add(&lru->hlink, &obj->hheads[hash]);
lru->value = value;
}
```
* MMM3 出現的形式與 MMM2 類似, 都是要走訪整個 list 因此選 ```list_for_each_entry```
* MMM4 出現於 15 行, 先看 14 行的條件為當 cache 滿的時候才成立, 根據 LRU 設計的原則這時候我們需要找出 least recently used element, 將它移出 list
而因為我們選擇將 least recently used element 維持在 list 的 tail, 因此使用 ```list_last_entry``` 可以直接找出最後元素, 並將其移除
## Q4. LeetCode 128. Longest Consecutive Sequence
```c=
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
struct seq_node {
int num;
struct list_head link;
};
static struct seq_node *find(int num, int size, struct list_head *heads)
{
struct seq_node *node;
int hash = num < 0 ? -num % size : num % size;
list_for_each_entry (node, &heads[hash], link) {
if (node->num == num)
return node;
}
return NULL;
}
int longestConsecutive(int *nums, int n_size)
{
int hash, length = 0;
struct seq_node *node;
struct list_head *heads = malloc(n_size * sizeof(*heads));
for (int i = 0; i < n_size; i++)
INIT_LIST_HEAD(&heads[i]);
for (int i = 0; i < n_size; i++) {
if (!find(nums[i], n_size, heads)) {
hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size;
node = malloc(sizeof(*node));
node->num = nums[i];
list_add(&node->link, &heads[hash]);
}
}
for (int i = 0; i < n_size; i++) {
int len = 0;
int num;
node = find(nums[i], n_size, heads);
while (node) {
len++;
num = node->num;
list_del(&node->link);
int left = num, right = num;
while ((node = find(++left, n_size, heads))) {
len++;
list_del(&node->link);
}
while ((node = find(--right, n_size, heads))) {
len++;
list_del(&node->link);
}
length = len > length ? len : length;
}
}
return length;
}
```
### 解題思路
從 longestConsecutive 函式看起, 一開始會先建立 n_size 個 heads 作為 hash 的 bucket
* 第 30 行開始的 for 迴圈會先讀過整個 nums , 並且到對應的 bucket 查詢是否以存在, 題目中的輸入數字可能會重複, 但解答時不需紀錄這些重複數字, 因此重複的部份會忽略, 而其餘部份會根據 hash value 加入到對應的 heads
* 第 39 行正式開始解題的環節, 再度用一個 for 迴圈看過整個 nums , 並且每個回合以 ```nums[i]``` 作為中心點開始向更大還有更小的數做查詢
* 第 48 行將 left, right 設定為 num, 但我們想知道更大以及更小的結果是否存在, 因此將 ```++``` ```--``` 放在前面讓這個運算可以先發生, 再開始查詢, 如果有查到的話則可以將該回合的結果 len + 1, 同時將 node 刪除後繼續往更大或更小的數字查詢
* 最後根據該回合結果看是否需要更新最後的回傳值 length, 等到整個迴圈跑完後將 length 回傳即可得到解答
## TODO
補圖
Sign in with Wallet
Connect another wallet