删除链表中重复的元素

方法一：直接删除重复的节点

图解：

链接

思路：

1.判断链表是否为空，如果为空，就直接返回null

2.由于进行删除，所以可以定义一个虚的头结点

3.遍历链表，如果遇到前后两个节点相等，就进行内循环，找到不重复的点

4.将重复的点跳过

** 代码：**

import java.util.*;
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        //判断一下如果链表为空,就直接不需要进行删除，返回null
        if(head==null){
            return null;
        }
        //由于进行删除操作的时候，头结点很特殊，所以可以通过设置一个虚的头结点，连接到原来的表上
        ListNode dummynode=new ListNode(-1);
        dummynode.next=head;
        ListNode cur=dummynode;
        //遍历整个表，只要当前的节点的下一个节点和下下个节点不为空，就继续进行循环
        //当遇到cur.next.val==cur.next.next.vald的时候，就需要进行一个内层的循环，跳过重复的点
        //只要cur后面还有节点，并且那个点的值与前面的值相等，那么就跳过这些点
        while(cur.next!=null&&cur.next.next!=null){
            if(cur.next.val==cur.next.next.val){
                int temp=cur.next.val;
                while(cur.next!=null&&cur.next.val==temp){
                    cur.next=cur.next.next;
                }
            }else{
                //否则如果不存在重复的就直接指向相邻的下一个节点
                cur=cur.next;
            }
        }
        return dummynode.next;

    }
}

方法二：哈希（适用于有序无序的链表的去重）

思路：

这道题幸运的是链表有序，我们可以直接与旁边的元素比较，然后删除重复。那我们扩展一点，万一遇到的链表无序呢？我们这里给出一种通用的解法，有序无序都可以使用，即利用哈希表来统计是否重复。

**具体做法：

step 1：遍历一次链表用哈希表记录每个节点值出现的次数。

step 2：在链表前加一个节点值为0的表头，方便可能的话删除表头元素。

step 3：再次遍历该链表，对于每个节点值检查哈希表中的计数，只留下计数为1的，其他情况都删除。

step 4：返回时去掉增加的表头。

java代码：

import java.util.*;
public class Solution {
    //用哈希的方法：适用于有序和无序的链表的去重
    public ListNode deleteDuplicates (ListNode head) {
        //先判断一下链表如果是空，就不需要进行删除，直接返回null
       if(head==null){
          return null;
       }
       //否则就创建一个HashMap
       //将对应节点的数值和该节点出现的个数存入map中
       Map<Integer,Integer> map=new HashMap<>();
       ListNode cur=head;
       while(cur!=null){
        if(map.containsKey(cur.val)){
            map.put(cur.val,(int)map.get(cur.val)+1);
        }else{
            map.put(cur.val,1);
        }
        cur=cur.next;
       }
       //由于要进行删除操作，又由于头结点是特殊的，所以可以定义一个虚的头结点
       //连接到原链表上
       //遍历链表的节点，如果发现该节点出现的次数不止一次，就跳过该节点
       ListNode dummynode=new ListNode(-1);
       dummynode.next=head;
       cur=dummynode;
       while(cur.next!=null){
           if(map.get(cur.next.val)!=1){
            cur.next=cur.next.next;
           }else{
            cur=cur.next;
           }
       }
        return dummynode.next;
    }
}

c++代码：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead==NULL){
            return pHead;
        }
        //定义一个哈希表：unordered_map是没有进行排序的只是类似数组的一一映射的关系
        //所以是可以通过直接调用下标来获得值的
        //而对于红黑树：map，是根据关键字进行排序的，是没有直接引用下标的
        //定义一个哈希表：对应的额两个是某个节点的值对应的出现的次数
        unordered_map<int,int> mp;
        ListNode* cur=pHead;
        //遍历整个链表，将对应的值记录到哈希表中
        while(cur!=NULL){
            mp[cur->val]++;
            cur=cur->next;
        }
        //进行删除操作和建立一个新表的时候，为了方便处理头结点
        //可以设置一个虚的头结点，将该虚的头结点连接到原链表的头结点
        ListNode* dummynode=new ListNode(-1);
        dummynode->next=pHead;
        cur=dummynode;
        //遍历每个节点，将个数不是1的节点跳过
        while(cur->next!=NULL){
            if(mp[cur->next->val]!=1){
            cur->next=cur->next->next;
            }else{
                cur=cur->next;
            }
        }
        return dummynode->next;
        

    }
};