面试题 02.01

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]. Follow Up:

How would you solve this problem if a temporary buffer is not allowed?

Solutions

1. hashset

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if (!head) return head;
        unordered_set<int> seen;
        ListNode * root = head, * prev = nullptr;
        while (head) {
            if (seen.count(head->val))
                prev->next = head->next;
            else {
                seen.insert(head->val);
                prev = head;
            }
            head = head->next;
        }

        return root;
    }
};

1. straight forward