---
tags: linux2022
---

# 2022q1 Homework1 (quiz1)

contributed by < `KatherineHuangg` >

## Q2
### 題目：
* 針對 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)，以下是可能的合法 C 程式實作

#include <stddef.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    if (head->next && head->val == head->next->val) {
        /* Remove all duplicate numbers */
        while (head->next && head->val == head->next->val)
            head = head->next;
        return deleteDuplicates(head->next);
    }

    head->next = deleteDuplicates(head->next);
    return head;
}

* :::success
延伸問題：
1. 嘗試避免遞迴，寫出同樣作用的程式碼
2. 以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼
:::
### 解題：
* 本題的目的是要從一個已排序好的 singly linked list 移除所有重複的節點，首先先來解析上面 code 的思路：
* ListNode結構：

digraph ListNode {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> val | <ref>  }", width=1.2]
        a:ref:c -> NULL
       
}

* 而關於這題的解法拆成以下三個部份：
1. `第 10~11 行：` 若條件成立則進到迴圈並 return
2. `第 13~18 行：` 若條件成立則進到迴圈並 return
3. `第 20 行：` 若 1、2皆不成立時
* **第 10 行**

    if (!head)
        return NULL;

* 是當 head 為空或是判斷到 singly linked list的尾端時會進到 if 條件判斷式並 return NULL
* **第 13 行**

    if (head->next && head->val == head->next->val)

* 這個 if 條件判斷式是需要先確認 `head->next` 是否為 NULL 以確保
`head->val` 跟 `head->next->val` 皆存在並可以比較 `val` 是否相同
* **第15行**

    while (head->next && head->val == head->next->val)
        head = head->next;

* 透過 while loop remove 掉數值相同的連續節點，而又因為當程式執行到 13~18 行時代表`head->val` 和 `head->next->val` 的值相同，`head` 本身也是需要 remove 掉的節點，所以第 17 行傳入 `deleteDuplicates()` 的參數也會是 `head->next`
* **第20行**
* 最後的第 20 行 ，因為上述的 13~18 行已判斷是否有重複的節點並 remove ，並確保了目前的 `head` 不會與其他資料重複，所以只要透過 `deleteDuplicates()` 來找到 `head->next` 指到的是哪個節點即可。

### 圖解步驟：
`Initial State:`

digraph ListNode {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> 1 | <ref>  }"]
        b [label="{ <data> 2 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        NULL [shape=box];
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:d -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:d -> NULL      [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}

`Step 1:`

`Step 2:`

### 延伸問題1.
* 嘗試避免遞迴，寫出同樣作用的程式碼

digraph ListNode {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> 12 | <ref>  }", width=1.2]
        b [label="{ <data> 99 | <ref>  }"];
        c [label="{ <data> 37 | <ref>  }"];
        d [shape=box];
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d      [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}