203. Remove Linked List Elements

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

Solution 1: add a sentinel to make the two conditions removing at the beginning and removing in the middle to be one condition.

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* removeElements(ListNode* head, int val) {
12         ListNode* sentinel=new ListNode(-1);
13         ListNode* pre=sentinel, *cur=head;
14         sentinel->next=head;
15         while(cur){
16             if (cur->val==val){
17                 pre->next=cur->next;
18                 cur=pre->next;
19             }
20             else {
21                 cur=cur->next;
22                 pre=pre->next;
23             }
24         }
25         return sentinel->next;
26     }
27 };

Solution 2: only use one pointer. line 10 free the memory of the deleted node to avoid the memory leak.

 1 class Solution {
 2 public:
 3     ListNode* removeElements(ListNode* head, int val) {
 4         ListNode* sentinel=new ListNode(-1), *pre=sentinel;
 5         sentinel->next=head;
 6         while(pre->next){
 7             if (pre->next->val==val){
 8                 ListNode* delptr=pre->next;
 9                 pre->next=pre->next->next;
10                 delete delptr;
11             }
12             else pre=pre->next;
13         }
14         return sentinel->next;
15     }
16 };

Solution 3: use recursion

1 class Solution {
2 public:
3     ListNode* removeElements(ListNode* head, int val) {
4         if (head==NULL) return NULL;
5         head->next = removeElements(head->next, val);
6         return head->val == val ? head->next : head;
7     }
8 };

consider freeing the deleted node memory

 1 class Solution {
 2 public:
 3     ListNode* removeElements(ListNode* head, int val) {
 4         if (head==NULL) return NULL;
 5         head->next = removeElements(head->next, val);
 6         if (head->val==val){
 7             ListNode* next=head->next;
 8             delete head;
 9             return next;
10         }
11         else return head;
12     }
13 };