删除链表中重复的结点

import java.util.*;
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    //(1)直观解法
    public ListNode deleteDuplication(ListNode pHead)
    {
       if(pHead==null||pHead.next==null)
        return pHead;
       LinkedHashMap<Integer,Integer>link=new LinkedHashMap<>();
       while(pHead!=null){
           if(!link.containsKey(pHead.val))
           {
               link.put(pHead.val,1);
           }else{

                link.put(pHead.val,2);
           }
           pHead=pHead.next;

       }

       ListNode head=new ListNode(1);
       ListNode rHead=null;
       int count=0;
       for(int i:link.keySet())
       {
            if(link.get(i)==1)
            {
                 head.next=new ListNode(i);
                 if(count==0)
                 {
                     rHead=head.next;
                     ++count;
                 }

                 head=head.next;
            }
       }

       return rHead;

    }

    //(2)添加头节点法
     public ListNode deleteDuplication2(ListNode pHead){
            if(pHead==null||pHead.next==null)
                  return pHead;
            //添加一个头节点
             ListNode first=new ListNode(-1);
             first.next=pHead;
             ListNode p=pHead;
             ListNode last=first;
             while(p!=null&&p.next!=null){

                  if(p.val==p.next.val){
                      int val=p.val;
                      while(p!=null&&p.val==val){
                          p=p.next;
                      }
                      last.next=p;
                  }else{
                      last=p;
                      p=p.next;
                  }
             }
             return first.next;

     }

    public static void main(String[]args){
        //System.out.println("Hello");
        ListNode head=new ListNode(1);
        head.next=new ListNode(2);
        head.next.next=new ListNode(3);
        head.next.next.next=new ListNode(3);
        head.next.next.next.next=new ListNode(4);
        head.next.next.next.next.next=new ListNode(4);
        head.next.next.next.next.next.next=new ListNode(5);
        Solution  s=new Solution();
        ListNode p=s.deleteDuplication2(head);
        while(p!=null){
             System.out.println(p.val);
             p=p.next;
        }

    }
}