remove-linked-list-elem

Problem

Analysis

  • with linked lists, if we are removing something we may need to update head
  • value can occur multiple times so we need to remove both
  • traversing linked list takes O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 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 == nullptr) return head;
        ListNode *p = head;

        // handle val(s) at head
        while (p && (p->val == val)) {
            ListNode *t = p;
            p = p->next;
            delete t;
        }
        // we need to update the head
        // if we deleted any nodes above
        head = p;

        // if no more nodes just return
        if !(head) return head;

        // handle the rest of the list
        while (p->next) {
            if (p->next->val == val) {
                ListNode* t = p->next;
                p->next = p->next->next;
                delete t;
            }
        }

        return head;
    }
};

Next Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * 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 == nullptr) return head;
        ListNode *p = head;

        // handle val(s) at head
        while (p && (p->val == val)) {
            ListNode *t = p;
            p = p->next;
            delete t;
        }
        // we need to update the head
        // if we deleted any nodes above
        head = p;

        // if no more nodes just return
        if (!head) return head;

        // handle the rest of the list
        while (p && p->next) {
            if (p->next->val == val) {
                ListNode* t = p->next;
                p->next = p->next->next; // point to the node after next
                delete t; // delete the next one
            }
            p = p->next; // move to next node
        }

        return head;
    }
};

Almost Final Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 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 == nullptr) return head;
        ListNode *p = head;

        // handle val(s) at head
        while (p && (p->val == val)) {
            ListNode *t = p;
            p = p->next;
            delete t;
        }
        // we need to update the head
        // if we deleted any nodes above
        head = p;

        // if no more nodes just return
        if (!head) return head;

        // handle the rest of the list
        ListNode *prev = p;
        ListNode *cur = p->next;
        while (cur) {
            ListNode* t = nullptr;
            if (cur->val == val)) {
                t = cur;
                prev->next = cur->next; // point to the node after next
            }
            cur = cur->next; // move to next node
            if (t) delete t;
        }

        return head;
    }
};

Final Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) return head;
        ListNode *p = head;

        // handle val(s) at head
        while (p && (p->val == val)) {
            ListNode *t = p;
            p = p->next;
            delete t;
        }
        // we need to update the head
        // if we deleted any nodes above
        head = p;

        // if no more nodes just return
        if (!head) return head;

        // handle the rest of the list
        ListNode *prev = p;
        ListNode *cur = p->next;
        while (cur) {
            //if (cur) { cout << cur->val << endl; }
            ListNode* t = nullptr;
            if (cur->val == val) {
                t = cur;
                prev->next = cur->next; // point to the node after next
            } else {
                // prev is only updated if we don't delete a node
                prev = cur;
            }
            cur = cur->next; // always move to next node

            if (t) delete t;
        }

        return head;
    }
};

Amended Solution

While the above solution is functional, it’s pretty long. We can remove the need for the special case of the val being at the head by using some pointer magic.

TODO: add picture

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