remove-linked-list-elements

Remove Linked List Elements – LeetCode 203

Problem

Description

Remove all elements from a linked list of integers that have value val.

Example

Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
Return: 1 –> 2 –> 3 –> 4 –> 5

Answer

Original

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        
        ListNode* now = dummy;
        ListNode* last;
        
        while(now){
            if(now->val != val){
                last = now;
                now = now->next;
            } else {
                last->next = now->next;
                now  = now->next;
            }
        }
        return dummy->next;
    }
};

思路

构造伪头节点，然后向后遍历移除目标元素，时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$26$ ms，排名$42.55\%$

Better

思路

递归解，缺点在于会大量消耗栈空间，只是展示一下。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$26$ ms，排名$42.55\%$

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (!head) return NULL;
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};