摸魚時卷王在瘋狂刷題，這我可忍不了-＜移除鏈表元素＞

題目要求

鏈接：https://leetcode-cn.com/problems/remove-linked-list-elements/description/

解題思路

遍歷鏈表進行對比，判斷是不是要洗掉的結點

要保存釋放結點的下一個結點，所以要定義兩個指標，不然就找不到下一個結點了

cur：用于遍歷鏈表，初始化 ： 指向頭結點

prev ：保存cur的上一個結點 初始化為：NULL

• 如果cur指向的是要洗掉的結點：

  • 先保存下一個結點 prev->next = cur->next
  • 釋放cur指向的結點 free(cur)
  • 然后把cur指向下一個結點 cur = prev->next （prev->next就是原來cur的下一個結點）

• 如果cur指向的不是要刪的結點：prev和cur迭代往后走

  • prev保存現在cur的位置 prev = cur
  • cur指向下一個位置 cur = cur -> next

特殊情況：要洗掉的是頭結點

• 此時要釋放原來的頭結點，然后更改頭指標的指向

• 步驟：

  • 1.先保存頭結點的下一個位置 cur = cur->next
  • 2.釋放頭結點 free(head)
  • 3.更改頭指標的指向：head = cur

  ---

  或者：

  head = cur->next;//換頭
  free(cur);//釋放原來的頭結點
  cur = head;//cur指向新的頭
  

錯誤寫法：

free(head);
head = cur->next;
cur = head;

錯誤原因：

提前釋放了頭結點，已經找不到它的下一個位置了

cur -> next 是野指標

代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
    //鏈表為空，回傳空
    if(head == NULL)
    {
        return NULL;
    }
    //定義兩個指標，cur用于遍歷，prev用于保存cur的上一個結點
    struct ListNode* prev = NULL;//若prev最初也指向head是有風險的
    struct ListNode* cur = head;
    while(cur)
    {
        //如果cur指向的是要刪的元素
        if(cur->val == val)
        {
            //特殊情況：要刪的是頭
            if(cur == head)
            {
                //釋放原來的頭結點，換頭
                head = cur->next;//換頭
                free(cur);//釋放原來的頭結點
                cur = head;//cur指向新的頭
            }
            else
            {
                prev->next = cur->next;//保存下一個結點
                free(cur);//釋放cur指向結點
                cur = prev->next;//cur指向下一個結點
            }
        }
        //如果cur指向的不是要洗掉的元素
        else
        {
            //prev保存的是cur的前一個結點
            prev = cur;//prev指向cur
            cur = cur->next;//cur迭代往后走
        }
        
    }
    return head;
}

prev若初始化為head的風險

為了保險起見：最初 prev = NULL

錯誤寫法

和上面的不同點:

當cur指向的是要洗掉的結點時：

• 用prev保存cur的下一個結點

下面正確寫法是：用prev->next指向cur的下一結點

struct ListNode* removeElements(struct ListNode* head, int val){
    //鏈表為空，回傳空
    if(head == NULL)
    {
        return NULL;
    }
    //定義兩個指標，cur用于遍歷，prev用于保存cur的上一個結點
    struct ListNode* prev = NULL;//若prev最初也指向head是有風險的
    struct ListNode* cur = head;
    while(cur)
    {
        //如果cur指向的是要刪的元素
        if(cur->val == val)
        {
            //特殊情況：要刪的是頭
            if(cur == head)
            {
                //釋放原來的頭結點，換頭
                head = cur->next;//換頭
                free(cur);//釋放原來的頭結點
                cur = head;//cur指向新的頭
            }
            else
            {
                prev = cur->next;//保存下一個結點   ->有問題！！！！！！！
                free(cur);//釋放cur指向結點
                cur = prev->next;//cur指向下一個結點
            }
        }
        //如果cur指向的不是要洗掉的元素
        else
        {
            prev = cur;//prev指向cur
            cur = cur->next;//cur迭代往后走
        }
        
    }
    return head;
}

錯誤原因：