题解 | #删除链表中重复的结点#

暴力解法，可以用HashSet记录重复的元素，一个一个删除，但是要遍历链表两次，O(N),O(N)

O(N), O(1)

链表题目，最好都加一虚拟头结点，有利用统一操作，不需要分开单独处理头结点

只需要一次遍历的时候，如果cur,cur.next指针的元素值相等，就一直向后移动cur指针，直到cur指针和此重复值不相等，结束，然后可以一起删除这些重复值（此时pre和cur指针中间的值）

如果cur,cur.next指针的元素值不相等，pre和cur都向后移动一次即可

因为有虚拟头结点的缘故，所以最后要去掉此虚拟结点，即返回dummy.next

import java.util.*;
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
    ListNode dummy = new ListNode(0);
    dummy.next = pHead;
    
    ListNode pre = dummy;
    ListNode cur = pHead;
    
    while(cur != null && cur.next != null){
        if(cur.val == cur.next.val){
            int val = cur.val;
            cur = cur.next;//此操作可有可无，有的话，少循环一次.也可以cur = cur.next.next;
            while(cur != null && cur.val == val){//向后移动cur
                cur = cur.next;
            }
            pre.next = cur;//mark，删除操作;
        }else{
            pre = cur;
            cur = cur.next;
        }
    }
    
    return dummy.next;
}
}