leetCode 203--チェーンテーブル要素を除去(C言語版)

タイトル

           val      。

  :

  : 1->2->6->3->4->5->6, val = 6
  : 1->2->3->4->5

構想設計
方法1
ヘッダノードを削除する可能性があることを考慮して、ヘッダノードの前にダミーノードdummyNodeを追加し、他のノードと同じようにヘッダノードを処理することができます.チェーンテーブルを直接先頭ノードから遍歴し、削除条件に合致した場合に直接削除すればよい.ノードを返すときはdummyNode->nextを直接返し、ヘッダノードが削除されないようにヘッダノードを返さないでください.
じょうふごう

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/**
* dummyNode     ，     ，            ，            。
*/
struct ListNode *removeElements(struct ListNode *head, int val)
{
	struct ListNode *dummyNode;
	dummyNode->next = head; //         
    struct ListNode *node = dummyNode;
    while (node->next) 
    {
        if (val == node->next->val)
        {
            node->next = node->next->next; //         node = node->next
        }else{  //                ，     else ,  node = node->next               
        node = node->next;
        }
    }
    return dummyNode->next;
}

方法2
ヘッダノードに発生する可能性のある特殊な状況について議論する.ヘッドノードが空で、ヘッドノードを削除する必要があります
じょうふごう

struct ListNode *removeElements(struct ListNode *head, int val)
{
	//        
    while (head && val == head->val)
    {
        head = head->next;
    }

	//      
    if (!head)
    {
        return head;
    }
    
    struct ListNode *node = head;
    while (node&&node->next) //   next               ，       node    
    {
        if (val == node->next->val)
        {
            node->next = node->next->next;
        }else{
        node = node->next;
    }}
    return head; //          ，              head
}

複雑度分析
時間複雑度以上の2つの方法はいずれもチェーンテーブルに対して1回のみ遍歴し,操作回数はnであるため,時間複雑度がO(n)空間複雑度以上の2つの方法はいずれも定数レベルのポインタのみを用い,空間複雑度がO(1)である.