面试题 02.01. 移除重复节点

面试题 02.01. 移除重复节点

借助set

/**
 * 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) {
        ListNode* pseudoHead = new ListNode();
        ListNode* ret = pseudoHead;
        unordered_set<int> set;
        while(head)
        {
            if(set.emplace(head->val).second)
            {
                pseudoHead->next = head;
                pseudoHead = pseudoHead->next;
            }
            head = head->next;
        }
        pseudoHead->next = nullptr;
        return ret->next;
    }
};

T(n) : O(n)

S(n) : O(n)

不用set(遍历好多次)

/**
 * 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) {
        auto point = head;
        while(point)
        {
            auto pre = point;
            auto cur = point->next;
            while(cur)
            {
                if(cur->val == point->val)
                {
                    pre->next = cur->next;
                    cur = cur->next;
                }else
                {
                    pre = pre->next;
                    cur = cur->next;
                }
            }
            point = point->next;
        }
        return head;
    }
};

T(n) : O(n^2)

S(n) : O(1)