---
tags: linux2022
---

# 2022q1 Homework1 (quiz1)
contributed by < [nckusaniel](https://github.com/nckusaniel) >

## Q1

## 測驗 2
針對 LeetCode 82. 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 (COND1) {
        /* Remove all duplicate numbers */
        while (COND2)
            head = head->next;
        return deleteDuplicates(head->next);
    }

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

### 想法與思路
把程式碼拆解並討論。
#### 第一個if

if (!head)
    return NULL;

代表head為NULL，並return NULL，
是遞迴呼叫的中止條件，可能情況如下
1. 串列根本不存在
2. 串列已經探索到最後一個節點

#### 第二個if

    if (COND1) {
        while (COND2)
            head = head->next;
        return deleteDuplicates(head->next);
    }

代表第一個if不成立，即 1.串列非空 2.還沒到尾巴

if成立 -> while成立-> head指到下一點 ->直到while不成立-> 遞迴呼叫head->next

探討：
if成立---發現重複的節點（不知道有幾個重複節點所以用while
while成立-- 跳過這些重複節點
while不成立-- head!=head->next，head停在重複節點中的最後一點

return deleteDuplicates(head->next);
    }

**我們不要這些重複節點，因此遞迴呼叫head->next來判斷下一點之情形**

#### 第三個狀況

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

會執行上述程式碼，代表輸入的參數head，不符合前兩個if，即head符合以下條件
1. 非空串列，且尚未探索至最後一點
2. head!=head->next,且沒有發現重複的節點
因此保留head，且想知道head->next之情形，因此呼叫deleteDuplicates(head->next)

##### COD1
判斷是否與下一點相同
**head->val ==head->next->val**
:::danger
1. head->next可能是NULL，因此沒有val取用，而發生錯誤所以要加上head->next!=null
2. 若是「head->next && head->val ==head->next->val」,先判斷next是否存在,再判斷是否相同就沒問題。但「head->val ==head->next->val && head->next」就錯誤因為head->next->val可能為NULL但沒有先判斷
:::

COD1= **head->next && head->val ==head->next->val**

##### COD2
跳過重複節點
COD2=**head->next && head->val ==head->next->val**

:::success
延伸問題:

1.嘗試避免遞迴，寫出同樣作用的程式碼
2.以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式
:::