如何删除链表中重复数据

数据结构与算法

1.最笨办法

就是遍历出所有数据放入Set。然后重新建表，，，。，。

class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}
public class Test {
    //    获取有的链表重复
    public static ListNode getListNode() {
        ListNode head = null;
        ListNode p = null;
        for (int i = 0; i < 10; i++) {
            if (head == null) {
                head = new ListNode(i);
                p = head;
            } else {
                ListNode node = new ListNode(i);
                p.next = node;
                p = p.next;
            }
        }
        ListNode node = new ListNode(3);
        p.next = node;
        return head;
    }
    //打印链表
    public static void print(ListNode head) {
        while (null != head) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
    public static void main(String[] args) {
//        print(getListNode());
        ListNode list = getListNode();
        print(list);
        //去重
        Set<Integer> set = new HashSet<>();
        ListNode head = list;
        while (null != head) {
            set.add(head.val);
            head = head.next;
        }
        System.out.println();
        //重建
        ListNode p = null;
        for (Integer i : set) {
            ListNode node = new ListNode(i);
            if (p == null) {
                p = node;
                head = p;
            } else {
                head.next = node;
                head = head.next;
            }
        }
        print(p);
    }
}

2.不用一次遍历完再重建，直接中途判断跳过

      public static void main(String[] args) {
// //        print(getListNode());
        ListNode list = getListNode();
        print(list);
//         //去重
        Set<Integer> set = new HashSet<>();
        ListNode head = list;
        while (head != null) {
            if (set.contains(head.next.val)) {
                head.next = head.next.next;
            } else {
                set.add(head.val);
            }
            head = head.next;
        }
        System.out.println();
        print(list);
    }

关于跳中间一个找前一个点。前一个点就是当前点，当前的next不为空的情况下分两种情况，一种是当前点的.next.next仍不为空，说明可以跳过，若为空，说明这是表尾。直接把当前点的next置空就可以了。

3.这个有点像筛选法

 public static void main(String[] args) {
//        print(getListNode());
        ListNode list = getListNode();
        print(list);
        //去重
        ListNode p=list;
        ListNode q=list;
        while(null!=p){
            q=p;
            while(null!=q.next){
                if(p.val==q.next.val){
                    q.next=q.next.next;
                }else {
                    q=q.next;
                }
            }
            p=p.next;
        }
        System.out.println();
        print(list);
    }