82.md

【中规中矩】82. 删除排序链表中的重复元素 II （C++,Python各两种解法）

解题思路

解法1：如果开始没有好的思路。最容易想到的方法就是两次遍历法。建立一个hash map，第一次遍历收集每个节点值的频率。第二次遍历删除那些节点频率大于1的节点，因为链表是排序的，不会出现相同节点值但不连续的情况。为了方便删除可以建立一个dummy node，让其next指向开始的head,这样不管原来的head是否被删除了，我们都返回head = dummy->next即可。

解法2：仔细想想其实我们没有必要两次遍历。我们完全可以找到所有连续的相同元素的节点组，用组前的指针pre指向组内的最后一个元素的next即可（注意C++需要for循环将组内的节点逐个delete掉，python，java内存自动管理，不用程序员操心），最后也是返回dummy->next.

如果喜欢我的题解，麻烦点赞转发评论，谢谢大家！

代码

class Solution1 {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }

        unordered_map<int, int> mp;
        auto cur = head;
        while (cur != nullptr) {
            mp[cur->val]++;
            cur = cur->next;
        }

        auto dummy = new ListNode();
        dummy->next = head;
        auto prev = dummy;
        cur = head;
        while (cur != nullptr) {
            if (mp[cur->val] > 1) {
                auto next = cur->next;
                prev->next = next;
                delete cur;
                cur = next;
            } else {
                prev = cur;
                cur = cur->next;
            }
        }

        head = dummy->next;
        delete dummy;
        return head;
    }
};

class Solution2 {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head)
            return NULL;
        ListNode* dummy = new ListNode(-1);
        ListNode* pre = dummy;
        ListNode* cur = head;
        dummy->next = cur;
        
        while (cur) {
            // Move forward the current pointer until the last same number
            while (cur->next && cur->val == cur->next->val)
                cur = cur->next;
            
            // no duplicated number
            if (pre->next == cur) {
                pre = cur;
                cur = cur->next;
            } else {
                auto p = pre->next;
                while (p != cur) {
                    auto next = p->next;
                    delete p;
                    p = next;
                }
                pre->next = cur->next;    
                delete cur;
                cur = pre->next;
            }
        }
        
        head = dummy->next;
        delete dummy;
        return head;
    }
};

class Solution1(object):
    def deleteDuplicates(self, head):
        if (not head or not head.next) :
            return head

        mp = dict()
        cur = head
        while (cur != None) :
            mp[cur.val] = mp.setdefault(cur.val, 0) + 1
            cur = cur.next
        
        dummy = ListNode(-1, head)
        dummy.next = head
        prev = dummy
        cur = head
        while (cur != None) :
            if (mp[cur.val] > 1) :
                next = cur.next
                prev.next = next
                cur = next
            else :
                prev = cur
                cur = cur.next
            
        

        head = dummy.next
        return head


class Solution(object):
    def deleteDuplicates(self, head):
        if (not head or not head.next) :
            return head

        dummy = ListNode(-1)
        pre = dummy
        cur = head
        dummy.next = cur
        
        while (cur) :
            # Move forward the current pointer until the last same number
            while (cur.next and cur.val == cur.next.val) :
                cur = cur.next
            
            # no duplicated number
            if (pre.next == cur) :
                pre = cur
                cur = cur.next
            else :
                pre.next = cur.next
                cur = pre.next
        
        head = dummy.next
        return head

点我赞赏作者

github 题解