2022q1 Homework1 (quiz 1)

contributed by < void110916 >

測驗題

測驗 1

測驗 2

#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;
}

1. 先判斷輸入的 list 是否指向 NULL (代表 list 結束)，是的話回傳 NULL ;否則接續。
2. 先判斷下一個 list 是否指向 NULL（否則後面判斷會有無法 dereference 的問題），是的話再判斷下一個 list 的值是否跟上一個的值一樣，若一樣的話做下列事：
   1. 將 head 指標指向最後一個值一樣的位置
   2. 回傳傳參為該位置的下一個 list 的 deleteDuplicates
3. 若下一個 list 的值跟上一個的值不一樣，則繼續將下一個 list 從 1. 點重新檢查。

此方法有以下特點：

• list 指向 NULL 的判斷有兩種意義：

  • list 是空的
  • list 已經搜尋到結尾

  因此若該 list 有

  $n$ 個 list (
  $n\ge 0$, NULL為0個)，則會呼叫函式
  $n+1$ 次