LeetCode: Remove Duplicate Node LCCI

Write code to remove duplicates from an unsorted linked list.

Example1:

Input: [1, 2, 3, 3, 2, 1]
Output: [1, 2, 3]

Example2:

Input: [1, 1, 1, 1, 2]
Output: [1, 2]

Note:

The length of the list is within the range[0, 20000].

The values of the list elements are within the range [0, 20000].

Solution #1: Use extra memory to store element’s count

Since there is a fiexed value range, we can use a array to set flags for occured elements. Then, when we iterate the linked list, we test whether the current element occurred in array.

If not occured, insert it into final result. Otherwise, skip it.

Time complexity is O(N), space complexity is O(M), where M is the max value of element.

Use a dummy node to make code more simpler:

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        vector<int> table(20001, 0);
        ListNode dummy;
        dummy.next = 0;
        ListNode* cur = &dummy;
        ListNode* p = head;
        while(p) {
            if(table[p->val] == 0) {
                table[p->val] = 1;
                cur->next = p;
                cur = cur->next;
                p = p->next;
                cur->next = 0;
            } else  {
                p = p->next;
            }
        }
        return dummy.next;
    }
};

Solution #2: Scan twice

For the follow-up challenge, we can use more time to save memory. For each current node, we iterate the left LinkedList and skip all the nodes which with the same value of the current node.

Time complexity: O(N^2)

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        ListNode* ob = head;
        while (ob != nullptr) {
            ListNode* oc = ob;
            while (oc->next != nullptr) {
                if (oc->next->val == ob->val) {
                    oc->next = oc->next->next;
                } else {
                    oc = oc->next;
                }
            }
            ob = ob->next;
        }
        return head;
    }
};

Join my Email List for more insights, It's Free!😋

← LeetCode: Groups of Special-Equi... LeetCode: Relative Sort Array →