[LeetCode Road] Remove Linked List Elements - Solution/C++

203. Remove Linked List Elements

Question:

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

Example:

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

Source code

Version 1

Idea:
Some inputs maybe like 1->1->2->3->null (val=1) or 1->1->1 (val=1), you have to do check to filer these elements at 16-18.

At 20-22 line, I declare a new ListNode, and link to head.
At 23-30 line, you should check the next value of head's element whether it'e equal to val, if it is true at 24 line, it will link to after the next element.

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

Version 2

Idea:
Declaring a new ListNode to recode the elements won't be necessary, you only delcare a pointer to point head, and return head at last.

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