力扣刷题10--移除重复节点

清疚 2023-02-26 13:25 11阅读 0赞

**题目**

**编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。**

示例1:
    
     输入：[1, 2, 3, 3, 2, 1]
     输出：[1, 2, 3]
     
    示例2:
    
     输入：[1, 1, 1, 1, 2]
     输出：[1, 2]

提示：
    
    链表长度在[0, 20000]范围内。
    链表元素在[0, 20000]范围内。

进阶：

如果不得使用临时缓冲区，该怎么解决？

[力扣出处面试金典][Link 1]

**解析**

设置一个临时缓冲区`unord_set<int> set`，用以保存未被重复的数字。  
![在这里插入图片描述][20200715213503197.png]  
**代码**

/** * 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) { 
            unordered_set<int> set;
            ListNode* current = head;
            while(current && current->next)
            { 
                set.insert(current->val);
                if(set.count(current->next->val))
                    current->next = current->next->next;
                else
                    current = current->next;            
            }
            return head;
        }
    };
    // hmtian@ 2020/7/15

**unordered\_set的count函数**

**1 if an element with a value equivalent to k is found, or zero otherwise.**

也就是说，count函数只会返回1或者0，如果找到相同的元素返回1否则相反。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA_size_16_color_FFFFFF_t_70]  
执行用时主要还是看的自己电脑CPU的性能，差一点也就问题不大。

**借鉴的优秀做法**

**思路描述：既然是移除重复节点，也就是需要 hash 表存储已经存在的节点，然后检查到重复之后删除掉就好了。**

[出处][Link 2]

/** * 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) { 
            int nodes[20001] = { 0};
            if(head == NULL) return head;
            ListNode* h = head->next, *pre = head;
            nodes[head->val] = 1;
            while(h){ 
                if(nodes[h->val]){ 
                    pre->next = h->next;
                    ListNode* cur = h;
                    h = h->next;
                    cur->next = NULL; delete(cur);
                }else{ 
                    nodes[h->val] = 1;
                    pre = h;
                    h = h->next;
                }
            }
            return head;
        }
    };

[Link 1]: https://leetcode-cn.com/problems/remove-duplicate-node-lcci/
[20200715213503197.png]: /images/20230209/71f15ca5185642ae8a97a6f44fbadbda.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200715212415295.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA==,size_16,color_FFFFFF,t_70
[Link 2]: https://leetcode-cn.com/problems/remove-duplicate-node-lcci/solution/c-hashbiao-yi-ci-bian-li-by-yizhe-shi/