Simple O(n) solution without worrying about pointers


  • 0
    M
    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head1) {
            stack <pair< int, int>> s;
            
            while (head1) {
                if (!s.empty() && s.top().first == head1->val) {
                    s.top().second++;
                } else {
                    s.emplace(make_pair(head1->val, 1));
                }
                head1 = head1->next;
            }
        
           ListNode *head = NULL;
            
            while (!s.empty()) {
                int n = s.top().first;
                int m = s.top().second;
                s.pop();
                if (m != 1)
                 continue;
                ListNode *tmp = new ListNode(n);
                tmp->next = head;
                head = tmp;
            }
            
            return head;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.