20. 删除重复元素

时间限制：30.000S 空间限制：128MB

题目描述

根据一个递增的整数序列构造有序单链表，删除其中的重复元素

输入描述

输入包括多组测试数据，每组测试数据占一行，第一个为大于等于0的整数n，表示该单链表的长度，后面跟着n个整数，表示链表的每一个元素。整数之间用空格隔开

输出描述

针对每组测试数据，输出包括两行，分别是删除前和删除后的链表元素，用空格隔开

如果链表为空，则只输出一行，list is empty

输入示例

5 1 2 3 4 5

5 1 1 2 2 3

0

输出示例

1 2 3 4 5

1 2 3 4 5

1 1 2 2 3

1 2 3

list is empty

解法一(模拟)

思路分析:

1. 手动实现链表
2. 使用Set哈希来去除重复的元素

实现代码如下:

public class k_20_RemoveDuplicateElements {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n;
        while (in.hasNext()) {
            n = in.nextInt();
            ListNode first = new ListNode();
            ListNode end = first;
            while (n-- > 0) {
                end.next = new ListNode(in.nextInt());
                end = end.next;
            }
            if (first.next == null) {
                System.out.println("list is empty");
            } else {
                // 输出链表
                printList(first.next);
                // 去重
                removeDuplicateEle(first.next);
                // 输出去重结果
                printList(first.next);
            }
        }
    }
    // 去除链表中的重复元素
    private static void removeDuplicateEle(ListNode list) {
        Set<Integer> elements = new HashSet<>();
        // 遍历链表
        ListNode p = list;
        ListNode pre = new ListNode();
        pre.next = p;
        while (p != null) {
            if (!elements.contains(p.val)) {
                elements.add(p.val);
                pre = pre.next;
            } else {
                pre.next = p.next;
            }
            p = p.next;
        }
    }
    // 输出链表
    private static void printList(ListNode start) {
        while (start != null) {
            System.out.print(start.val + " ");
            start = start.next;
        }
        System.out.println();
    }
    // 自定义链表
    public static class ListNode {
        int val;
        ListNode next;

        public ListNode() {
        }

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

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

提交结果如下:

复杂度分析:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$