2022q1 Homework1 (quiz1)

contributed by < 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，
是遞迴呼叫的中止條件，可能情況如下

串列根本不存在
串列已經探索到最後一個節點

第二個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符合以下條件

非空串列，且尚未探索至最後一點
head!=head->next,且沒有發現重複的節點
因此保留head，且想知道head->next之情形，因此呼叫deleteDuplicates(head->next)

COD1

判斷是否與下一點相同
head->val ==head->next->val

head->next可能是NULL，因此沒有val取用，而發生錯誤所以要加上head->next!=null
若是「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

延伸問題:

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