2019-02-19

java删除链表中重复的节点（保留一个节点）

package cn.exercise.list;

import java.util.HashMap;

/**
 * 删除链表重复节点(重复节点只保留一个)
 */
public class DeleteDuplecate {
    /**
     * HashMap,时间复杂度o(n)
     * @param head
     * @return
     */
    public static ListNode deleteDulp(ListNode head){
        if(head==null || head.next==null)
            return head;
        HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
        ListNode p=new ListNode(-1);//加一个头结点
        p.next=head;
        ListNode pre=p;//两个一前一后临时指针
        ListNode cur=p.next;
        while(pre!=null && pre.next!=null){
            if(map.containsKey(cur.val)){
                pre.next=cur.next;
                cur=cur.next;
            }else{
                map.put(cur.val,1);
                pre=cur;
                cur=cur.next;
            }
        }
        return p.next;
    }

    /**
     * 双重循环遍历链表,时间复杂度o(n^2)
     * @param head
     * @return
     */
    public static ListNode deleteDulp2(ListNode head){
        if(head==null || head.next==null)
            return head;
        ListNode p=head;
        ListNode root=p;
        while(p!=null){
            ListNode q=p;
            while(q.next!=null){
                if(p.val==q.next.val){
                    q.next=q.next.next;
                }else{
                    q=q.next;
                }
            }
            p=p.next;
        }
        return root;
    }
    public static void main(String[] args){
        ListNode root=new ListNode(1);
        ListNode b=new ListNode(2);
        ListNode c=new ListNode(4);
        ListNode d=new ListNode(2);
        ListNode e=new ListNode(5);
        ListNode f=new ListNode(4);
        ListNode g=new ListNode(3);
        ListNode h=new ListNode(5);
        root.next=b;
        b.next=c;
        c.next=d;
        d.next=e;
        e.next=f;
        f.next=g;
        g.next=h;
        while(root!=null){
            System.out.print(root.val+" ");
            root=root.next;
        }
        System.out.print("after:");
        ListNode pre=deleteDulp2(root);

        while(pre!=null){
            System.out.print(pre.val+" ");
            pre=pre.next;
        }
    }
}

before:1 2 4 2 5 4 3 5
结果：
after:1 2 4 5 3