删除链表中重复的结点

淩亂°似流年 2022-05-24 06:07 195阅读 0赞

![这里写图片描述][70]

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;
            }
    
        }
    }

![这里写图片描述][70 1]

[70]: /images/20220524/79cd017b41d2471a9e11135fd6445e72.png
[70 1]: /images/20220524/c25118657c41493ba9d536a79d350d50.png