【LeetCode】203. Remove Linked List Elements

Question link

Link

Intuition

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
(給定一個鏈結串列與整數，移除掉所有鏈結串列中等於val的節點並回傳新的head)

題意要求移除掉ListNode的值符合val時要移除掉，也就是在遍歷過程中，如果遇到下一個節點是符合條件的，就將其跳過連接到下下一個節點。

1. Dummy Node Approach
   • 為了避免需要處理掉如果一開始的head->val就等於val情況，我可以先創建虛擬節點或者又稱哨兵節點，來進行處理
2. Indirect Pointer Approach
   • 使用間接指標來進操作每一個節點中的next指標，這樣就不需要額外的dummy node了，藉由改變指標(view-point)，來進行操作，view-point 指得是從操作struct ListNode* 變成操作其next的指標
     Linus Torvalds 在 TED 2016 的訪談

Approach

1. Dummy Node Approach
   • 建立一個dummy，並進行初始化，將其 next 節點指向 head。
   • 建立一個 ptr 指標作為遍歷時的操作指標，並將其指向dummy
   • 迴圈遍歷整個鏈結串列，直到沒有下一個節點，也就是 ptr->next 為 NULL
     • 檢查下個節點的值是否等於val，是則將next指向下下一個節點也就是next->next
     • 否則更新 ptr，指向下一個節點
   • 最後回傳 dummy->next
2. Indirect Pointer Approach
   • 建立間接指標 ptr 指向 head 指標
   • 迴圈遍歷，直到 *ptr 為空指標
     • 如果ptr指標指向的指標中的值等於 val，就將其鏈接到下下一個指標
     • 否則就更新ptr，將其指向next指標
   • 最後直接回傳head

在Indirect Pointer Approach中需要練習如何解讀指標的指標並進行操作

• ptr 為間接指標，其中儲存的值是指向指標的地址
• *ptr 為dereference間接指標，依照儲存的地址去取值，也就是取得其指向指標的值，其回傳型態為struct ListNode*

Complexity

• Time complexity:
  $O(n)$
• Space complexity:
  $O(1)$

Code

Solution 1

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;
    struct ListNode* ptr = dummy;
    while (ptr->next) { 
        if (ptr->next->val == val) {
            ptr->next = ptr->next->next;
        }
        else{
            ptr = ptr->next;
        }
    }
    struct ListNode* result = dummy->next;
    free(dummy);
    return result;
}

Solution 2

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode **ptr = &head;
    while (*ptr){
        if ((*ptr)->val == val){
            *ptr = (*ptr)->next;
        }
        else {
            ptr = &(*ptr)->next;
        }
    }
    return head;
}