---
tags: linux2022
---

# 2022q1 Homework1 (quiz)
contributed by < `AxotZero` >

## Q2: Remove Duplicates from Sorted List II

### Original Question
COND1 = `head->next && head->val == head->next->val`
COND2 = `head->next && head->val == head->next->val`
> Haven't figured out whether there is another way to complete these two conditions.

### Extension Question
#### For-loop version
Inspired from [案例探討: Leetcode 2095. Delete the Middle Node of a Linked List](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List), I tried to use ptr2ptr to solve this problem and reduce branch of this program.

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;
    struct ListNode **ptr = &head, **cur = ptr;
    while(*cur){
        while((*cur)->next && (*ptr)->val == (*cur)->next->val){
            cur = &(*cur)->next;
        }
        // there are duplicates
        if(ptr != cur){ 
            *ptr = (*cur)->next;
        }
        else{
            ptr = &(*cur)->next;
        }
        cur = ptr;
    }
    return head;
}

#### Doubly Linked List For-loop

> Still figuring out the better way to simplify the code

## Q3: [LRU Cache](https://leetcode.com/problems/lru-cache/)
### Original Question
- MMM1: `list_for_each_entry_safe`
- Because in `lRUCacheFree`, It needs to delete all the container of each `list_head`. Hence, we need a `safe` pointer which represent the next node of current node that will be delete.
- MMM2 and MMM3: `list_for_each_entry`
- The goal of MMM2 and MMM3 are the same. Both of them aim to find out the target node. The diffirence between (MMM2, MMM3) and MMM1 is that (MMM2, MMM3) won't delete the node. Hence, we don't need a `safe` pointer.
- MMM4: `list_last_entry`
- since everytime we `get` and `put` value from cache, the program will move the target node to the first. Hence, the last element will be the least recently used element.

### Extension Question
TODO

## Q4: [128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/description/)
### Origin Question
#### The snippet of the code

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(LLL, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            while ((node = find(RRR, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            length = len > length ? len : length;
        

1. LLL = `--left` and RRR = `++right`
2. LLL = `++left` and RRR = `--right`
- Because we have already ++len in the line 6, we have to do `pre-decrement` / `pre-increment` operation to make program correct.

### Extension Question
TODO