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, 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

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

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