online advertising

Wednesday, August 12, 2015

LeetCode OJ - Remove Linked List Elements

Problem:

Please find the problem here.

Solution:

I approached the problem using a fake head.

Imagine you have a left hand side starting the list with a fake head, and keeping track of the last element added to the list.

We will use the given example:

F -> NULL, 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> NULL

Then we move the nodes to the left hand side one by one as appropriate.

F -> 1, 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> NULL
F -> 1 -> 2, 6 -> 3 -> 4 -> 5 -> 6 -> NULL
F -> 1 -> 2, 3 -> 4 -> 5 -> 6 -> NULL
F -> 1 -> 2 -> 3, 4 -> 5 -> 6 -> NULL
F -> 1 -> 2 -> 3 -> 4, 5 -> 6 -> NULL
F -> 1 -> 2 -> 3 -> 4 -> 5, 6 -> NULL
F -> 1 -> 2 -> 3 -> 4 -> 5, NULL

Note that now we will stop because the head variable is NULL, but in fact we haven't fix the last pointer of 5 pointing to 6 yet, so we have to fix that one to make sure it does point to NULL, and that's it.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/remove-linked-list-elements/

#include "LEET_REMOVE_LINKED_LIST_ELEMENTS.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_REMOVE_LINKED_LIST_ELEMENTS
{
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };

    class Solution
    {
    public:
        ListNode* removeElements(ListNode* head, int val)
        {
            ListNode fakeHead(10086);
            ListNode* last = &fakeHead;
            fakeHead.next = head;
            while (head != NULL)
            {
                if (head->val != val)
                {
                    last->next = head;
                    last = head;
                }
                head = head->next;
            }

            last->next = NULL;

            return fakeHead.next;
        }
    };
};

using namespace _LEET_REMOVE_LINKED_LIST_ELEMENTS;

int LEET_REMOVE_LINKED_LIST_ELEMENTS()
{
    Solution solution;
    ListNode a(1);
    ListNode b(2);
    ListNode c(6);
    ListNode d(3);
    ListNode e(4);
    ListNode f(5);
    ListNode g(6);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;
    f.next = &g;
    ListNode* deleted = solution.removeElements(&a, 6);
    while (deleted != NULL)
    {
        cout << deleted->val << ", ";
        deleted = deleted->next;
    }
    cout << endl;
    return 0;
}

No comments :

Post a Comment